Inclusion Criteria:

* STEP 1 REGISTRATION (RANDOMIZATION): Patients must have clinically detectable stage III (clinically detectable N1b, N1c, N2b, N2c, N3b and N3c) or stage IV resectable melanoma. Patients with melanoma of mucosal or acral origin are eligible. Patients with melanoma of uveal origin are not eligible. Patients with a history of brain metastases are not eligible. Clinically detectable is defined as disease that is apparent and measurable via physical examination or radiographic imaging.
* STEP 1 REGISTRATION (RANDOMIZATION): Patients are eligible for this trial either at initial presentation of their melanoma or at the time of the first detected nodal, satellite/in-transit, distant metastases, or recurrent disease in prior lymphadenectomy basin or distant site. Nodal, satellite/in-transit metastasis, distant metastases or disease in a prior complete lymphadenectomy basin must have been confirmed histologically by hematoxylin (H) \& eosin (E) stained slides.
* STEP 1 REGISTRATION (RANDOMIZATION): Patients with multiple regional nodal basin involvement are eligible. Gross or microscopic extracapsular nodal extension is permitted.
* STEP 1 REGISTRATION (RANDOMIZATION): Patients must have histologically proven stage IIIB or higher. This would entail pathologic confirmation beyond the primary or initial diagnosis of melanoma involving fine needle aspiration cytology or biopsy confirmation of any N-category or M-category resectable site.
* STEP 1 REGISTRATION (RANDOMIZATION): Patients must not have received previous neoadjuvant treatment for their melanoma. Patients may have received prior non-immunotherapy adjuvant therapy. Patients must not have had prior immunotherapy including, but not limited to ipilimumab, interferon alfa-2b, high dose interleukin (IL)-2, pegylated-interferon (PEG-IFN), anti-PD-1, anti-PD-L1 intra-tumoral, or vaccine therapies. Patients must not be planning to receive any of the prohibited therapies during treatment phases on the study.
* STEP 1 REGISTRATION (RANDOMIZATION): Patients must not be planning to receive concomitant other biologic therapy, hormonal therapy, other chemotherapy, surgery, while on protocol therapy.
* STEP 1 REGISTRATION (RANDOMIZATION): Patients may have received prior radiation therapy, including after prior surgical resection. All adverse events associated with prior surgery and radiation therapy must have resolved to =\< grade 1 prior to randomization.
* STEP 1 REGISTRATION (RANDOMIZATION): Patients must be \>= 18 years of age
* STEP 1 REGISTRATION (RANDOMIZATION): All patients must have disease status documented by a complete physical examination and imaging studies within 42 days prior to randomization. Imaging studies must include a CT of the chest, abdomen and pelvis with intravenous contrast (unless contraindicated). For patients with melanoma arising from the head and neck, dedicated neck imaging (CT with intravenous contrast is required. If the patient has unknown primary with disease in the axilla, neck imaging is required CT imaging must be done with intravenous contrast if there are no contraindications for it. Extremity melanomas must be imaged using CT with intravenous contrast or MRI with and without gadolinium

* Note: PET-CT scans are NOT acceptable to establish eligibility. Non-iodinated CT scans that are part of common PET-CT imaging protocols do not provide contrast for difficult to ascertain areas such as the neck and liver, and do not provide enough CT detail to perform appropriate RECIST 1.1 measurements. As such, a PET-CT with non-contrast CT or non-diagnostic quality CT images is considered insufficient for the detection of melanoma.
* STEP 1 REGISTRATION (RANDOMIZATION): All patients must have a CT or magnetic resonance imaging (MRI) of the brain within 42 days prior to randomization. The brain CT or MRI should be performed with intravenous contrast (unless contraindicated).
* STEP 1 REGISTRATION (RANDOMIZATION): Absolute neutrophil count (ANC) \>= 1,500/microliter (mcL) (within 42 days prior to randomization).
* STEP 1 REGISTRATION (RANDOMIZATION): Platelets \>= 100,000/mcL (within 42 days prior to randomization).
* STEP 1 REGISTRATION (RANDOMIZATION): Hemoglobin \>= 10 g/dL (within 42 days prior to randomization).
* STEP 1 REGISTRATION (RANDOMIZATION): Total bilirubin =\< 1.5 x institutional upper limit of normal (IULN) (except patients with Gilbert's syndrome, who must have a total bilirubin \< 3.0 mg/dL) (within 42 days prior to randomization).
* STEP 1 REGISTRATION (RANDOMIZATION): Serum glutamic-oxaloacetic transaminase (SGOT) (aspartate aminotransferase \[AST\]) and serum glutamate pyruvate transaminase (SGPT) (alanine aminotransferase \[ALT\]) =\< 2 x IULN (within 42 days prior to randomization).
* STEP 1 REGISTRATION (RANDOMIZATION): Alkaline phosphatase =\< 2 x IULN (within 42 days prior to randomization).
* STEP 1 REGISTRATION (RANDOMIZATION): Patients must have lactate dehydrogenase (LDH) performed within 42 days prior to randomization.
* STEP 1 REGISTRATION (RANDOMIZATION): Patients must have adequate renal function as evidenced by calculated creatinine clearance \> 30 mL/min. The creatinine level (mg/dL) used in the calculation must be obtained within 42 days prior to randomization.
* STEP 1 REGISTRATION (RANDOMIZATION): Patients must have Zubrod performance status =\< 2.
* STEP 1 REGISTRATION (RANDOMIZATION): Patients must not have a history of (non-infectious) pneumonitis that required steroids or current pneumonitis.
* STEP 1 REGISTRATION (RANDOMIZATION): Patients must not have an active infection requiring systemic therapy.
* STEP 1 REGISTRATION (RANDOMIZATION): Patients must not have active autoimmune disease that has required systemic treatment in past 2 years (i.e., with use of disease modifying agents, corticosteroids or immunosuppressive drugs). Replacement therapy (e.g., thyroxine, insulin, or physiologic corticosteroid replacement therapy for adrenal or pituitary insufficiency, etc.) is not considered a form of systemic treatment.
* STEP 1 REGISTRATION (RANDOMIZATION): Patients must not have received live vaccines within 42 days prior to randomization. Examples of live vaccines include, but are not limited to, the following: measles, mumps, rubella, chicken pox, shingles, yellow fever, rabies, Bacillus Calmette-Guerin (BCG), and typhoid (oral) vaccine. Seasonal influenza vaccines for injection are generally killed virus vaccines and are allowed; however, intranasal influenza vaccines (e.g., Flu-Mist) are live attenuated vaccines, and are not allowed.

* NOTE: The COVID-19 vaccines (currently available and those in the pipeline for FDA emergency use authorization or FDA approval) do not contain live virus, and therefore, COVID-19 vaccination does not affect or preclude eligibility for the S1801 trial. For patients who have undergone lymphadenectomy, vaccines should be delivered to a limb with an intact lymph node basin (Sentinel lymph node biopsy in a limb is acceptable). The vaccine should not be administered in a limb that has undergone lymphadenectomy.
* STEP 1 REGISTRATION (RANDOMIZATION): Patients known to be human immunodeficiency virus (HIV) positive are eligible if they meet the following criteria within 30 days prior to randomization: stable and adequate CD4 counts (\>= 350 mm\^3), and serum HIV viral load of \< 25,000 IU/ml. Patients may be on or off anti-viral therapy so long as they meet the CD4 count criteria.
* STEP 1 REGISTRATION (RANDOMIZATION): Patients must not have known active hepatitis B virus (HBV) or hepatitis C virus (HCV) infection prior to randomization. Note: No testing for hepatitis B and hepatitis C is required unless mandated by local health authority.
* STEP 1 REGISTRATION (RANDOMIZATION): Prior malignancy is allowed providing it does not require concurrent therapy.
* STEP 1 REGISTRATION (RANDOMIZATION): Women of childbearing potential must have a negative urine or serum pregnancy test within 28 days prior to randomization. Women/men of reproductive potential must have agreed to use an effective contraceptive method for the course of the study through 120 days after the last dose of study medication. Should a woman become pregnant or suspect she is pregnant while she or her partner is participating in this study, she should inform her treating physician immediately. A woman is considered to be of "reproductive potential" if she has had menses at any time in the preceding 12 consecutive months. In addition to routine contraceptive methods, "effective contraception" also includes heterosexual celibacy and surgery intended to prevent pregnancy (or with a side-effect of pregnancy prevention) defined as a hysterectomy, bilateral oophorectomy, or bilateral tubal ligation. However, if at any point a previously celibate patient chooses to become heterosexually active during the time period for use of contraceptive measures outlined in the protocol, he/she is responsible for beginning contraceptive measures. Patients must not be pregnant or nursing due to unknown teratogenic side effects.
* STEP 1 REGISTRATION (RANDOMIZATION): Patients must be deemed medically fit to undergo surgery by the treating medical/surgical team.
* STEP 1 REGISTRATION (RANDOMIZATION): Patients must be willing to submit the following surgical specimens: either all tissue blocks from the surgical specimen or two slides per block (\[1\] hematoxylin and eosin \[H\&E\] slide and \[1\] unstained slide OR \[2\] unstained slides if H\&E stained slides cannot be provided).
* STEP 1 REGISTRATION (RANDOMIZATION): Patients must be offered the opportunity to participate in specimen banking.
* STEP 1 REGISTRATION (RANDOMIZATION): Patients must be informed of the investigational nature of this study and must sign and give written informed consent for this protocol in accordance with institutional and federal guidelines.
* STEP 1 REGISTRATION (RANDOMIZATION): As a part of the Oncology Patient Enrollment Network (OPEN) randomization process the treating institution's identity is provided in order to ensure that the current (within 365 days) date of institutional review board approval for this study has been entered in the system.
* STEP 2 REGISTRATION (SURGERY): Patients randomized to arm 2 (neoadjuvant arm) must be willing to submit tissue to determine pathologic response regardless of number of pre-operative doses of pembrolizumab (MK-3475) received. Determination of pathologic response cannot be done on less than the full surgical specimen.
* STEP 2 REGISTRATION (SURGERY): Patients must have disease assessments by CT chest/abdomen/pelvis with IV contrast, and neck CT with IV contrast if primary head and neck melanoma, performed within 42 days (and no more than 49 days) before the planned date of surgery. MRI combined with non-contrast CT is an acceptable alternative for patients with CT contrast allergy, but imaging must encompass total body.
* STEP 2 REGISTRATION (SURGERY): Patients must register to step 2 within 17 days prior to planned date of surgery.
* STEP 3 REGISTRATION (ADJUVANT THERAPY): Patients must have undergone surgery prior to Step 3 registration. The Step 2 surgery must have completely resected their melanoma.

* Patients with gross positive residual disease following surgery do not qualify as having disease-free status, and, therefore, such patients are not eligible to register for adjuvant therapy.
* Patients with microscopic residual disease (i.e., positive margins) can be treated with re-excision or radiation, per site discretion, to render the patient disease-free prior to registration of adjuvant therapy.
* Disease-free status must be documented by a complete physical examination and radiographic imaging studies within 42 days prior to Step 3 registration. Imaging studies must include a CT of the chest, abdomen, and pelvis (unless contraindicated). Extremity melanomas must be imaged using CT with intravenous contrast or MRI with and without gadolinium. CT imaging must be done with intravenous contrast if there are no contraindications for it.
* For patients with melanoma arising from the head and neck, dedicated neck imaging (CT with IV contrast, unless contraindicated) is required.
* If the patient has had unknown primary with disease in the axilla, neck imaging is required to assure the region is clear of cancer.
* Any other clinically indicated imaging studies if performed (e.g., bone scan) must show no evidence of disease.
* STEP 3 REGISTRATION (ADJUVANT THERAPY): Patients must be registered to step 3 no more than 84 days after date of surgery.
* STEP 3 REGISTRATION (ADJUVANT THERAPY): Patients with R0 or R1 resections must have disease-free status documented by a complete physical examination and imaging studies within 42 days prior to step 3 registration. These patients must have disease assessments by CT chest/abdomen/pelvis with IV contrast, and neck CT with IV contrast if primary head and neck melanoma. MRI combined with non-contrast CT is an acceptable alternative for patients with CT contrast allergy, but imaging must encompass total body.
* STEP 3 REGISTRATION (ADJUVANT THERAPY): Patients with R2 resections are not eligible for step 3 and must be removed from study treatment