Inclusion Criteria:  STEP 1 - SPECIMEN SUBMISSION INCLUSION CRITERIA  Participants must have histologically confirmed melanoma that is stage III or IV, unresectable, recurrent, or metastatic non-uveal melanoma OR Participants must have histologically confirmed squamous cell carcinoma of the head and neck (HNSCC) that is either locally recurrent and non-amendable to curative therapy (e.g., radiation, surgery) or metastatic. The primary tumor location must be the oropharynx, oral cavity, hypopharynx, or larynx. Primary tumor site of nasopharynx (any histology) or unknown primary tumor are not eligible  Note: For participants with primary oropharyngeal cancer, human papillomavirus (HPV) or p16 status must be known prior to step 1 registration Participants must have disease presentation consistent with measurable disease. Note: Current disease measurements will not be required until step 2 registration Participants must have had documented progression within 12 weeks after the last dose of PD-1 checkpoint inhibition-based therapy. Participants must have been receiving checkpoint inhibition for a minimum of 6 weeks prior to progression. Participants who recur during adjuvant anti-PD1 treatment or within 12 weeks of completion of adjuvant anti-PD1 treatment are eligible if they have measurable disease and considered unresectable Participants with known human immunodeficiency virus (HIV)-infection must be receiving anti-retroviral therapy and have an undetectable viral load test within 6 months prior to step 1 registration Participants with evidence of chronic hepatitis B virus (HBV) infection must have undetectable HBV viral load within 28 days prior to step 1 registration Participants with a history of hepatitis C virus (HCV) infection must have no detectable viral load within 28 days prior to step 1 registration Participants must have recovered to baseline or =< Grade 1 Common Terminology Criteria for Adverse Events (CTCAE) version (v) 5 toxicities related to any prior treatments, unless adverse events are deemed clinically nonsignificant by the treating investigator or stable on supportive therapy Participants must be >= 18 years of age Participants must have a Zubrod Performance Status 0 or 1 Participants must have adequate cardiac function. Participants with known history or current symptoms of cardiac disease, or history of treatment with cardiotoxic agents, must have a clinical risk assessment of cardiac function using the New York Heart Association Functional Classification and must be class 2B or better to be eligible for this trial Have adequate tissue specimen from procedure obtained within 6 months prior to step 1 registration and after development of resistance to anti-PD-1/L1 therapy. Archival tissue must consist of tumor block or at least 20 freshly cut serially sectioned and numbered 4-5 micron unstained, positively-charged slides OR  Be willing to undergo research biopsy AND have tumor accessible for biopsy based on the following criteria:  Mediastinal, laparoscopic, gastrointestinal, or bronchial endoscopic biopsies can be obtained incidentally to a clinically necessary procedure and NOT for the sole purpose of the clinical trial  Acceptable biopsy procedures are:  Percutaneous biopsy with local anesthetic and/or sedation with an expected risk of severe complications < 2% Direct transoral biopsy (with or without local anesthetic and/or sedation) with an expected risk of severe complications < 2% Excisional cutaneous biopsy with local anesthetic and/or sedation with an expected risk of severe complications < 2% Biopsy with removal of additional tumor tissue during a medically necessary mediastinoscopy, laparoscopy, gastrointestinal endoscopy, bronchoscopy or craniotomy. No open surgical, laparoscopic or endoscopic procedure should be performed solely to obtain a biopsy for this protocol  Removal of additional tumor tissue during a medically necessary surgical procedure  Participants must have been offered the opportunity to participate in specimen banking Note: As a part of the Oncology Patient Enrollment Network (OPEN) registration 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 Participants must be informed of the investigational nature of this study and must sign and give informed consent in accordance with institutional and federal guidelines  Participants with impaired decision-making capacity are eligible as long as their neurological or psychological condition does not preclude their safe participation in the study (e.g., tracking pill consumption and reporting adverse events to the investigator)  STEP 2 TREATMENT REGISTRATION INCLUSION CRITERIA Participants must have been eligible for step 1 registration Participants must have had their tumor tissue submitted via the Southwest Oncology Group (SWOG) Specimen Tracking System prior to step 2 registration Participants registered during stage II of the protocol must have received assignment to an open cohort from the SWOG Statistics and Data Management Center based on their biomarker screening profile (not applicable for patients registered during stage I of the protocol) Participants must have measurable disease. All measurable disease must be assessed within 28 days prior to step 2 registration. All non-measurable disease must be assessed within 42 days prior to step 2 registration. Note: All disease must be assessed and documented on the Baseline Tumor Assessment Form (Response Evaluation Criteria in Solid Tumors [RECIST] 1.1) For melanoma participants, computed tomography (CT) chest, abdomen and pelvis must be obtained. For HNSCC participants, CT neck and chest must be obtained. Further imaging (i.e., magnetic resonance imaging [MR] brain, CT abdomen/pelvis or extremities, bone scan) will be performed as deemed appropriate by the treating physician Participants with treated brain metastases must have no evidence of progression on the follow-up brain imaging after central nervous system (CNS)-directed therapy Participants with treated brain metastases must have discontinued steroid treatment at least 14 days prior to step 2 registration Participants must have a history and physical examination performed within 28 days prior to step 2 registration Participants must be able to take oral medication without breaking, opening, crushing, dissolving or chewing capsules Leukocytes >= 3,000/uL (within 28 days prior to step 2 registration) Absolute neutrophil count >= 1,500/uL (within 28 days prior to step 2 registration) Platelets >= 100,000/uL (within 28 days prior to step 2 registration) Total bilirubin =< 1.5 x institutional upper limit of normal (ULN) or =< 3 x ULN for participants with Gilbert's disease (within 28 days prior to step 2 registration) Aspartate aminotransferase (AST) =< 3 x institutional ULN (within 28 days prior to step 2 registration) Alanine aminotransferase (ALT) =< 3 x institutional ULN (within 28 days prior to step 2 registration) Urinalysis: For baseline value (no required value for eligibility) Fridericia corrected QT interval (QTcF) =< 450 milliseconds in male and =< 470 milliseconds in female on screening electrocardiogram (ECG) (within 28 days prior to step 2 registration) Creatinine =< 3 x institutional ULN (within 28 days prior to step 2 registration) OR Measured (OR calculated) creatinine clearance >= 30 mL/min using the Cockcroft-Gault formula. This specimen must have been drawn and processed within 28 days prior to Step 2 registration  Exclusion Criteria:  STEP 1 - SPECIMEN SUBMISSION EXCLUSION CRITERIA Participants must not have an active infection requiring systemic therapy (except HBV, HCV or HIV as mentioned above) Participants must not have received surgery, chemotherapy, radiation therapy, biologic agents, or steroids within 14 days prior to step 1 registration  Participants must not have received more than one prior primary radiotherapy regimen, curative or adjuvant, to the head and neck, with the additional following criteria:  If the primary radiation is combined with chemotherapy, a minimum of 16 weeks will be required to have elapsed between the end of radiotherapy and step 1 registration. If the radiation is given alone, a minimum of 8 weeks will be required to have elapsed between the end of radiotherapy and step 1 registration Additional palliative radiotherapy regimens are permitted but cannot have been administered to previously treated tissue (i.e., overlapping fields are excluded) and must be completed at least 4 weeks prior to step 1 registration Treatment areas should be healed with no sequelae from radiation therapy (RT) that would predispose to fistula formation Participants must not have received prior treatment with anti-VEGF therapies for any reason Participants must not have any known significant organ disfunction that, in the opinion of the treating investigator, may impact suitability for receiving combination nivolumab/cabozantinib treatment  Participants must not have active autoimmune disease requiring systemic steroids (equivalent of > 10mg of prednisone) or other immune suppression. Exceptions:  Type 1 diabetes mellitus Hypothyroidism only requiring hormone replacement Skin disorders (e.g., vitiligo, psoriasis, or alopecia) not requiring systemic treatment Conditions not expected to recur in the absence of an external trigger Participants must not have received an organ allograft Participants must not have a history of hemoptysis (defined as >= 1/2 tsp of bright red blood per day) or tumor bleeding within 90 days prior to step 1 registration Participants must not have known central lung lesions involving major blood vessels (arteries or veins) or a tumor encasing major blood vessels (e.g., carotid artery)  Participants must not require concomitant anticoagulation with coumarin agents (e.g., warfarin), direct thrombin inhibitors (e.g., dabigatran), direct factor Xa inhibitor betrixaban, or platelet inhibitors (e.g., clopidogrel)  Participants must not require anticoagulants except for the following:  Prophylactic use of low-dose aspirin for cardio-protection (per local applicable guidelines) and low-dose low molecular weight heparins (LMWH). Therapeutic doses of LMWH or anticoagulation with direct factor Xa inhibitors, rivaroxaban, edoxaban, or apixaban in participants without known brain metastases who are on a stable dose of the anticoagulant for at least 1 week prior to step 1 registration without clinically significant hemorrhagic complications from the anticoagulation regimen or the tumor Participants must not have evidence of preexisting uncontrolled hypertension prior to step 1 registration as documented by 2 baseline blood pressure readings taken at least 30 minutes apart within 28 days prior to step 1 registration. The baseline systolic blood pressure readings must be =< 150 mmHg and the baseline diastolic blood pressure readings must be =< 90 mmHg. Participants on antihypertensive therapies with controlled blood pressure are eligible Participants must not have a prior or concurrent malignancy whose natural history or treatment (in the opinion of the treating physician) has the potential to interfere with the safety or efficacy assessment of the investigational regimen Participants must not be pregnant or nursing due to the known safety profiles of the drugs in this study. Individuals who are of reproductive potential must have agreed to use an effective contraceptive method with details provided as a part of the consent process. A person who has had menses at any time in the preceding 12 consecutive months or who has semen likely to contain sperm is considered to be of "reproductive potential. In addition to routine contraceptive methods, "effective contraception" also includes refraining from sexual activity that might result in pregnancy and surgery intended to prevent pregnancy (or with a side-effect of pregnancy prevention) including hysterectomy, bilateral oophorectomy, bilateral tubal ligation/occlusion and vasectomy with testing showing no sperm in the semen STEP 2 TREATMENT REGISTRATION EXCLUSION CRITERIA Participants must not have experienced any significant health changes that, in the opinion of the treating investigator, may impact continued suitability for receiving combination nivolumab/cabozantinib treatment  Participants must not have received more than one prior primary radiotherapy regimen, curative or adjuvant, to the head and neck, with the additional following conditions:  If the primary radiation is combined with chemotherapy, a minimum of 16 weeks will be required to have elapsed between the end of radiotherapy and step 2 registration. If the radiation is given alone, a minimum of 8 weeks will be required to have elapsed between the end of radiotherapy and step 2 registration Additional palliative radiotherapy regimens are permitted but cannot have been administered to previously treated tissue (i.e., overlapping fields are excluded) and must be completed at least 4 weeks prior to step 2 registration Treatment areas should be healed with no sequelae from RT that would predispose to fistula formation Participants must not have received investigational agents or monoclonal antibodies (except Food and Drug Administration [FDA] approved supportive care antibodies, such as denosumab) within 28 days prior to step 2 registration Participants must not have received any prior treatment with anti-VEGF based therapies Participants must not have received administration of a live, attenuated vaccine within 30 days prior to step 2 registration. Note: Participants may have received a messenger ribonucleic acid (mRNA) or viral vector-based COVID-19 vaccine within 30 days prior to step 2 registration Participants must not have received administration of any strong CYP3A4 inhibitors, such as but not limited to clarithromycin, itraconazole, ketoconazole, grapefruit juice, indinavir, nelfinavir, ritonavir, nefazodone, saquinavir, and telithromycin, within 7 days prior to step 2 registration Participants must not have received administration of any strong CYP3A4 inducers, such as but not limited to rifampin, carbamazepine, enzalutamide, mitotane, phenytoin and St. John's wort, within 7 days prior to step 2 registration Participants must not have malabsorption syndrome Participants must not have central lung lesions involving major blood vessels (arteries or veins) or a tumor encasing major blood vessels (e.g., carotid artery)