• STEP 1 - SPECIMEN SUBMISSION

• 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 during or 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. 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 are 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 not have an active infection requiring systemic therapy (except HBV, HCV or HIV as mentioned above)

• Participants must not have experienced myocardial infarction or thromboembolic event requiring anticoagulation within 90 days prior to step 1 registration, unless clinically stable with ongoing medical management

• 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 not have received more than one prior primary radiotherapy regimen, curative or adjuvant, to the mucosal surfaces of 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) with the exception of central nervous system (CNS) radiation 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 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

• 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 be able to take oral medication without breaking, opening, crushing, dissolving or chewing capsules

• Participants must not have malabsorption syndrome

• Participants must not have active autoimmune disease requiring systemic steroids (equivalent of \> 10mg of prednisone) or other immune suppression. Exceptions:

‣ Type 1 diabetes mellitus

⁃ Endocrinopathy 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 any of the following criteria due to the possibility of increased risk for tumor bleeding with cabozantinib therapy:

‣ Prior carotid bleeding

⁃ Tumors that invade major vessels (e.g., the carotid) as shown unequivocally by imaging studies

⁃ Central (e.g., within 2 cm from the hilum) lung metastases that are cavitary as shown unequivocally by imaging studies

⁃ Any prior history of bleeding related to the current head and neck cancer

⁃ History of gross hemoptysis (bright red blood of 1/2 teaspoon or more per episode of coughing) within 3 months

• 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 28 days prior to step 1 registration as documented by baseline blood pressure reading with systolic blood pressure \> 150 mmHg and/or diastolic blood pressure \> 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

• Have an adequate archival tissue specimen verified by the local pathologist and documented on the Pathology Review Form from a procedure obtained after the development of resistance to anti-PD-1/L1 therapy. Archival tissue must consist of tumor block or at least 1 hematoxylin and eosin (H\&E)-stained 4-5 micron slide and 20 freshly cut serially sectioned and numbered 4-5 micron unstained, uncharged 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 submit whole blood for germline genomic analysis

∙ 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

• Note: No tests or exams are required to be repeated for step 2 registration (Treatment). However, participants who are known to have a change in eligibility status after step 1 registration are not eligible for step 2 registration

‣ Participants must continue to meet eligibility for step 1 registration prior to step 2 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, CT chest, abdomen and pelvis must be obtained. For HNSCC participants, CT neck and chest must be obtained. Further imaging (i.e., 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 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 with treated brain metastases must have discontinued steroid treatment at least 14 days prior to step 2 registration

⁃ 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 surgery, chemotherapy, radiation therapy, biologic agents, or steroids within 14 days prior to step 2 registration

⁃ 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 coronavirus disease 2019 (COVID-19) vaccine within 30 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 14 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 5 times the half-life of the CYP3A inhibitor prior to step 2 registration

⁃ Participants must have a history and physical examination performed within 28 days prior to step 2 registration

⁃ 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)

⁃ Measured (OR calculated) creatinine clearance \>= 30 mL/min using the following Cockcroft-Gault Formula. This specimen must have been drawn and processed within 28 days prior to step 2 registration