Neoadjuvant and Adjuvant Checkpoint Blockade

Inclusion Criteria:

* Capable of giving written informed consent, which includes compliance with the requirements and restrictions listed in the consent form
* Patients must have histologically or cytologically confirmed stage IIIB/C or stage IV oligometastatic melanoma; oligometastatic melanoma is defined as three or fewer areas of resectable disease excluding central nervous system and bone involvement; patients with cutaneous, mucosal, acral, ocular or unknown primary melanomas are eligible for enrollment; for patients with stage IV disease with distant lymph nodes (stage M1a), a maximum of three separate lymph node sites fit the definition of oligometastatic disease; resectable tumors are defined as having no significant vascular, neural or bony involvement; only cases where a complete surgical resection with tumor-free margins can safely be achieved are defined as resectable
* Patients will have at least one melanoma deposit that can undergo serial biopsy (at least 2 time points) during the neoadjuvant phase of the protocol; patients must be willing to provide tumor samples at the time points specified in the Study Procedure Tables
* All patients must undergo a baseline tumor biopsy; in Arms A and B, tumor biopsy for PD-L1 testing (PD-L1 positivity is determined by greater than or equal to 1% of cells staining in the membrane by immunohistochemistry) is required for stratification; PD-L1 status is not required for enrollment on Arm C; the 28-8 clone for PD-L1 testing is required for assessment of PD-L1 status; for patients with stage IV disease, site of tumor biopsy will preferably be from non-lymph node disease site; for PD-L1 testing, the biopsy should contain sufficient tumor content (\> 100 tumor cells/4-micron tissue section); if a sample contains insufficient tumor content, a re-biopsy will be required to obtain a sample with sufficient tumor content prior to treatment
* Patients must be medically fit enough to undergo surgery as determined by the treating medical and surgical oncology team
* Patients who have been previously treated in the adjuvant setting for melanoma will be eligible for treatment after a 28 day wash-out period
* Patients must have measurable disease, defined by RECIST 1.1
* Age \>/= 18 years
* Eastern Cooperative Oncology Group (ECOG) performance status 0-1
* Absolute neutrophil count (ANC) \>= 1.5 X 10\^9/L (within 28 days of first study treatment)
* Hemoglobin \>= 8.5 g/dL (within 28 days of first study treatment)
* Platelets \>= 100 X 10\^9/L (\>= 60 for hepatocellular carcinoma \[HCC\]) (within 28 days of first study treatment)
* Prothrombin time (PT)/international normalized ratio (INR) and partial thromboplastin time (PTT) =\< 1.5 X upper limit of normal (ULN) (within 28 days of first study treatment)
* White blood cells (WBC) \>= 2.0 X 10\^9/L (within 28 days of first study treatment)
* Total bilirubin =\< 1.5 X ULN (except subjects with Gilbert's syndrome who must have normal direct bilirubin) \[3 mg/dL for HCC\] (within 28 days of first study treatment)
* Aspartate aminotransferase (AST) and alanine aminotransferase (ALT) =\< 3.0 x upper limit of normal (ULN) (=\< 5 x ULN for HCC) (within 28 days of first study treatment)
* Albumin \>= 2.5 g/dL (within 28 days of first study treatment)
* Creatinine =\< 1.5 x ULN OR calculated creatinine clearance \>= 40 mL/min OR 24-hour urine creatinine clearance \>= 50 mL/min (within 28 days of first study treatment)
* Lipase \< 1.5 X ULN (within 28 days of first study treatment)
* Amylase \< 1.5 X ULN (within 28 days of first study treatment)
* Normal thyroid function (or stable on hormone supplementation) 0.27 - 10 X 10\^9/L (within 28 days of first study treatment)
* Left ventricular ejection fraction (LVEF) \>= 50% by transthoracic echocardiography (TTE) (preferred) or multigated acquisition (MUGA) within 6 months from first study drug administration
* Women are eligible to participate if: non-childbearing potential defined as pre-menopausal females with a documented tubal ligation or hysterectomy; or postmenopausal defined as 12 months of spontaneous amenorrhea (in questionable cases a blood sample with simultaneous follicle stimulating hormone \[FSH\] \> 40 MlU/mL and estradiol \< 40 pg/mL \[\< 140 pmol/L\] is confirmatory); females on hormone replacement therapy (HRT) and whose menopausal status is in doubt will be required to use one of the contraception methods if they wish to continue their HRT during the study; otherwise, they must discontinue HRT to allow confirmation of post-menopausal status prior to study enrollment; for most forms of HRT, at least 2-4 weeks will elapse between the cessation of therapy and the blood draw; this interval depends on the type and dosage of HRT; following confirmation of their post-menopausal status, they can resume use of HRT during the study without use of a contraceptive method
* A woman of childbearing potential (WOCBP) agrees to use method(s) of contraception; for a teratogenic study drug and/or when there is insufficient information to assess teratogenicity, a highly effective method(s) of contraception (failure rate of \< 1% per year) is required; the individual methods of contraception and duration should be determined in consultation with the investigator; WOCBP must follow instructions for birth control when the half-life of the study drug is \> 24 hours; contraception should be continued for a period of 30 days plus the time required for the study drug to undergo 5 half-lives; WOCBP should use an adequate method to avoid pregnancy for 24 weeks (30 days plus the time required for study drug to undergo 5 half-lives) after the last dose of study drug; WOCBP must have a negative serum or urine pregnancy test (minimum sensitivity 25 IU/L or equivalent units of human chorionic gonadotropin \[HCG\]) within 24 hours prior to the start of investigational product
* Women must not be breastfeeding
* Men who are sexually active with WOCBP must use any contraceptive method with a failure rate of \< 1% per year; the investigator shall review contraception methods and the time period that contraception must be followed; men who are sexually active with WOCBP must follow instructions for birth control when the half-life of the study drug is \> 24 hours, contraception should be continued for 90 days plus the time required for the study drug to undergo 5 half-lives; therefore, men who are sexually active with WOCBP must continue contraception for 33 weeks (90 days plus the time required for nivolumab and/or relatlimab to undergo 5 half-lives) after the last dose of study drug; in addition, male participants must be willing to refrain from sperm donation during this time; men who are sexually active with women who are not of childbearing potential (i.e., who are postmenopausal or surgically sterile and azoospermic men) do not require contraception
* For Arm C: Cardiac assessment at baseline by trans- thoracic echocardiogram (TTE) with LVEF 50%

Exclusion Criteria:

* Currently receiving cancer therapy (chemotherapy, radiation therapy, immunotherapy, or biologic therapy) or investigational anti-cancer drug
* Any major surgery within the last 3 weeks
* Brain metastases, leptomeningeal disease or bone metastases
* Pregnant or lactating female
* Unwillingness or inability to follow the procedures required in the protocol
* Current use of anticoagulants (warfarin, heparin, direct thrombin inhibitors) at therapeutic levels
* Any serious or uncontrolled medical disorder that, in the opinion of the investigator, may increase the risk associated with study participation or study drug administration, impair the ability of the subject to receive protocol therapy, or interfere with the interpretation of study results
* Prior malignancy active within the previous 3 years except for patient's prior diagnosis of melanoma and locally curable cancers that have been apparently cured, such as basal or squamous cell skin cancer, superficial bladder cancer, or carcinoma in situ of the prostate, cervix, or breast with local control measures (surgery, radiation)
* Subjects with active, known or suspected autoimmune disease; subjects with vitiligo, type I diabetes mellitus, residual hypothyroidism due to autoimmune condition only requiring hormone replacement, psoriasis not requiring systemic treatment, or conditions not expected to recur in the absence of an external trigger are permitted to enroll
* Subjects with a condition requiring systemic treatment with either corticosteroids (\> 10 mg daily prednisone equivalents) or other immunosuppressive medications within 14 days of study drug administration; inhaled or topical steroids and adrenal replacement doses \> 10 mg daily prednisone equivalents are permitted in the absence of active autoimmune disease
* Prior treatment with an anti-PD-1, anti-PD-L1, anti-LAG-3, or anti-CTLA-4 antibody
* Any positive test result for hepatitis B or C virus indicating acute or chronic infection
* Known history of testing positive for human immunodeficiency virus or known acquired immunodeficiency syndrome
* History of severe hypersensitivity reaction to any monoclonal antibody
* Prisoners or subjects who are involuntarily incarcerated
* Subjects who are compulsorily detained for treatment of either a psychiatric or physical (infection disease) illness
* A known or underlying medical condition that, in the opinion of the Investigator, could make the administration of the study drug hazardous to the subject or could adversely affect the ability of the subject to comply with or tolerate the study
* A confirmed history of encephalitis, meningitis, or uncontrolled seizures in the year prior to informed consent
* Evidence of active infection that requires systemic antibacterial, antiviral, or antifungal therapy 7 days prior to initiation of study drug therapy
* Any other acute or chronic medical illness
* Subjects who are unable to undergo venipuncture and/or tolerate venous access
* Any other sound medical, psychiatric, and/or social reason as determined by the Investigator
* Any of the following procedures or medications:

  * Within 2 weeks prior to time of study treatment:

    * Systemic or topical corticosteroids at immunosuppressive doses (\> 10 mg/day of prednisone or equivalent); inhaled or topical steroids, and adrenal replacement steroid doses of \> 10 mg daily prednisone equivalent, are permitted in the absence of active autoimmune disease
    * Palliative radiation or gamma
  * Within 4 weeks prior to study drug administration:

    * Any investigational cytotoxic drug; exposure to any non-cytotoxic drug within 4 weeks or 5 half-lives (whichever is shorter) is prohibited; if 5 half-lives is shorter than 4 weeks, agreement with sponsor/medical monitor is mandatory
* Subjects with history of life-threatening toxicity related to prior immune therapy (e.g., anti-CTLA-4 or anti-PD-1/PD-L1 treatment or any other antibody or drug specifically targeting T-cell co-stimulation or immune checkpoint pathways) except those that are unlikely to re-occur with standard countermeasures (e.g., hormone replacement after endocrinopathy)
* Troponin T (TnT) or I (TnI) \> 2 x institutional upper limit of normal (ULN); subjects with TnT or TnI levels between \> 1 to 2 x ULN will be permitted if repeat levels within 24 hours are \</= 1 x ULN; if TnT or TnI levels are \> 1 to 2 x ULN within 24 hours, the subject may undergo a cardiac evaluation and be considered for treatment, following a discussion with the investigator or designee; when repeat levels within 24 hours are not available, a repeat test should be conducted as soon as possible; if TnT or TnI repeat levels beyond 24 hours are \< 2 x ULN, the subject may undergo a cardiac evaluation and be considered for treatment, following a discussion with the investigator or designee
* For Arm C: Uncontrolled or significant cardiovascular disease including, but not limited to, any of the following:

  * Myocardial infarction (MI) or stroke/transient ischemic attack (TIA) within the 6 months prior to consent
  * Uncontrolled angina within the 3 months prior to consent
  * Any history of clinically significant arrhythmias (such as ventricular tachycardia, ventricular fibrillation, or torsades de pointes)
  * Corrected QT interval (QTc) prolongation \> 480 msec
  * History of other clinically significant cardiovascular disease (i.e., cardiomyopathy, congestive heart failure with New York Heart Association \[NYHA\] functional classification III-IV, pericarditis, significant pericardial effusion, significant coronary stent occlusion, deep venous thrombosis, etc )
  * Cardiovascular disease-related requirement for daily supplemental oxygen
  * History of two or more MIs OR two or more coronary revascularization procedures
  * Subjects with history of myocarditis, regardless of etiology