Inclusion Criteria:

          -  Histologically or cytologically confirmed recurrent or metastatic HNSCC of the oral
             cavity, larynx, hypopharynx, oropharynx, or p16 positive neck node with unknown
             primary (but clinically thought to be oropharynx).

          -  Known p16 status (positive or negative) if oropharynx or unknown primary of the neck.

          -  Measurable disease per RECIST. Measurable disease defined as lesions that can be
             accurately measured in at least one dimension (longest diameter to be recorded) as ≥
             10 mm with CT scan, as ≥ 20 mm by chest x-ray, or ≥ 10 mm with calipers by clinical
             exam.

          -  Progression of disease, as assessed by RECIST, that occurred on a PD-1 or PD-L1
             inhibitor (given alone or with other therapy) to treat recurrent or metastatic
             disease. Progression of disease that occurred on a PD-1 or PD-L1 inhibitor given as a
             component of a curative-intent regimen is excluded.

          -  PD-L1 CPS by IHC (22C3 antibody) on tumor tissue must be available or performed,
             although the test result is not required to enroll onto the trial. Patients with tumor
             PD-L1 TPS (but not CPS) available are also eligible; but, PD-L1 CPS must be performed
             in these cases. Fresh tumor tissue (obtained after progression on prior PD-1 or PD-L1
             inhibitor given for recurrent or metastatic disease) is strongly preferred, but
             archived tumor tissue from recurrence is also acceptable.

          -  At least 18 years of age.

          -  ECOG performance status < 1

          -  Normal bone marrow and organ function as defined below:

               -  Hemoglobin > 9 g/L

               -  Absolute neutrophil count ≥ 1,500/mcl

               -  Platelets ≥ 100,000/mcl (transfusion independent, defined as not receiving
                  platelet transfusions within 7 days prior to laboratory sample)

               -  Total bilirubin ≤ 1.5 mg/dL

               -  AST(SGOT)/ALT(SGPT) ≤ 2.5 x IULN (in cases of bone mets or liver mets, AST/ALT <
                  5 x IULN)

               -  Serum creatinine <1.5 x IULN or creatinine clearance > 50 mL/min by
                  Cockcroft-Gault

          -  The effects of nivolumab and nab-paclitaxel on the developing human fetus are unknown.
             For this reason and because monoclonal antibodies and antimicrotubule agents are known
             to be teratogenic, women of childbearing potential (WOCBP) and men must agree to use
             adequate contraception (hormonal or barrier method of birth control, abstinence) prior
             to study entry, for the duration of study participation, and for 6 months after the
             last dose of study treatment. Should a woman become pregnant or suspect she is
             pregnant while participating in this study, she must inform her treating physician
             immediately.

          -  Ability to understand and willingness to sign an IRB approved written informed consent
             document (or that of legally authorized representative, if applicable) before the
             performance of any protocol-related procedures.

        Exclusion Criteria:

          -  A history of other malignancy with the exception of malignancies for which all
             treatment was completed at least 1 year before registration and the patient has no
             evidence of disease.

          -  Has known active CNS metastases. Subjects with previously treated brain metastases may
             participate provided they are stable (without any evidence of progression by imaging 4
             weeks prior to the first dose of study treatment and any neurologic symptoms have
             stabilized), have no evidence of new or enlarging brain metastases, and are on stable
             or tapering doses of steroids for at least 14 days prior to first dose of study
             treatment.

          -  A history of serious allergic reactions attributed to compounds of similar chemical or
             biologic composition to agents used in the study (Allergic reaction to cetuximab is
             allowed as there are other standard of care options for the investigator's choice
             arm).

          -  Receiving systemic corticosteroid therapy (in doses exceeding 10 mg daily of
             prednisone equivalent) within 7 days prior to the first dose of treatment. A history
             of severe autoimmune disorder requiring high-dose corticosteroid treatment due to
             prior PD-1 inhibitor is an exclusion criterion.

          -  Greater than Grade 2 pre-existing peripheral neuropathy (per CTCAE).

          -  Uncontrolled serious intercurrent illness including, but not limited to, ongoing or
             active infection, symptomatic congestive heart failure, unstable angina pectoris, or
             cardiac arrhythmia.

          -  Pregnant and/or breastfeeding. Women of childbearing potential must have a negative
             serum pregnancy test within 24 hours prior to the start of study treatment.

          -  Prior organ or allogeneic stem cell transplant.

          -  Has an active autoimmune disease (i.e. rheumatoid arthritis, lupus, Sjogren's
             syndrome) that has required IV or subcutaneous systemic treatment in the past 6 months
             (excluding Rituxan). Replacement therapy (i.e. thyroxine, insulin, or physiologic
             corticosteroid replacement therapy for adrenal or pituitary insufficiency, etc.) is
             not considered a form of systemic treatment.

          -  Prisoners, or subjects who are compulsory detained.