This randomized pilot early phase I trial studies how well nivolumab with or without tadalafil work in treating patients with head and neck squamous cell carcinoma that has come back and can be removed by surgery. Monoclonal antibodies, such as nivolumab, may interfere with the ability of tumor cells to grow and spread. Tadalafil may stop the growth of tumor cells by blocking some of the enzymes needed for cell growth. Giving nivolumab and tadalafil may work better in treating patients head and neck squamous cell carcinoma.

PRIMARY OBJECTIVES:

I. To investigate whether adding the PDE5 inhibitor, tadalafil, to nivolumab therapy affects intratumoral and systemic anti-tumor immunity.

SECONDARY OBJECTIVES:

I. Characterize the combined effects of nivolumab and tadalafil on safety, exosome composition and function, the composition of intratumoral immune cell populations, wound healing, and tumor radiographic response.

Inclusion Criteria:

• Pathologically confirmed head and neck squamous cell carcinoma (HNSCC)
• Any stage HNSCC of the 1) oral cavity, 2) oropharynx, 3) larynx, 4) hypopharynx, 5) nasal cavity/paranasal sinuses, 6) unknown primary considered to have resectable disease; patients with recurrent disease that is amenable to surgery are eligible
• Eastern Cooperative Oncology Group (ECOG) performance status 0-2
• While blood cells 2000/ul or more
• Absolute neutrophil count 1500/ul or more
• Platelets 100,000/ul or more
• Hemoglobin 9 g/dl or more
• Bilirubin less than or equal to 1.5 x the upper limit of normal (except subjects with Gilbert syndrome, who can have total bilirubin < 3 mg/dl)
• Aspartate aminotransferase (AST) and alanine aminotransferase (ALT) less than or equal to 3 x the upper limit of normal
• Glomerular filtration rate (GFR) greater than or equal to 40 ml/min using the Cockcroft-Gault formula or serum creatinine less than or equal to 1.5 x upper limit of normal (ULN)
• Women of reproductive potential should have a negative serum or urine pregnancy test (minimum sensitivity 25 IU/L or equivalent units of human chorionic gonadotropin [HCG]) within 21 days of study enrollment
• Women of reproductive potential must use highly effective contraception methods to avoid pregnancy for 23 weeks after the last dose of study drugs; "women of reproductive potential" is defined as any female who has experienced menarche and who has not undergone surgical sterilization (hysterectomy or bilateral oophorectomy) or who is not postmenopausal; menopause is defined clinically as 12 months of amenorrhea in a woman over 45 in the absence of other biological or physiological causes; in addition, women under the age of 55 must have a documented serum follicle stimulating hormone (FSH) level more than 40 mIU/mL
• Men of reproductive potential who are sexually active with women of reproductive potential must use any contraceptive method with a failure rate of less than 1% per year; men who are receiving the study medications will be instructed to adhere to contraception for 31 weeks after the last dose of study drugs; men who are azoospermic do not require contraception
• All subjects must be able to comprehend and sign a written informed consent document

Exclusion Criteria:

• Patients with nasopharyngeal carcinoma, salivary gland or skin primaries
• Patients with any anginal chest pain; defined by a known diagnosis of angina; or defined by chest pressure, squeezing, radiating pain to arms, shoulders, or neck from the chest; with or without exertion
• Patients taking nitrates
• Patients taking PDE5 inhibitors more then 1/week during the previous 28 days
• Patients with a secondary condition (sickle cell anemia) that cause priapism
• Any history of a severe hypersensitivity reaction to any monoclonal antibody
• Any history of allergy to the study drug components
• Any concurrent malignancies; exceptions include- basal cell carcinoma of the skin, squamous cell carcinoma of the skin, superficial bladder cancer or in situ cervical cancer that has undergone potentially curative therapy; patients with a history of other prior malignancy must have been treated with curative intent and must have remained disease-free for 2 years post-diagnosis
• Any diagnosis of immunodeficiency or current immunosuppressive therapy including >10mg/day of prednisone within 14 days of enrollment is not permitted.
• Patients that have an active autoimmune disease requiring systemic treatment within the past 3 months or a documented history of clinically severe autoimmune disease, or a syndrome that requires systemic steroids (> 10 mg daily prednisone equivalents) or immunosuppressive agents; subjects with vitiligo, type I diabetes mellitus, or resolved childhood asthma/atopy would be an exception to this rule. Inhaled or topical steroids, and adrena replacement steroid doses =<10mg daily prednisone equivalent, are permitted in the absence of active autoimmune disease. Subjects that require intermittent use of bronchodilators or local steroid injections would not be excluded from the study; subjects with hypothyroidism stable on hormone replacement or Sjorgen's syndrome will not be excluded from the study
• Patients must not be receiving any other investigational agents
• Patients with uncontrolled intercurrent illnesses including, but not limited to an active infection requiring systemic therapy or a known psychiatric or substance abuse disorder(s) that would interfere with cooperation with the requirements of the trial
• Patients must not be pregnant or breastfeeding
• Patients with a known human immunodeficiency virus infection (HIV 1/2 antibodies) or acquired immunodeficiency syndrome (HIV/AIDS), active hepatitis B (e.g., hepatitis B surface antigen [HBsAg] reactive) or hepatitis C (e.g., hepatitis C virus [HCV] ribonucleic acid [RNA] [qualitative] is detected)
• Patients with any evidence of current interstitial lung disease (ILD) or pneumonitis
• Patients with prior history of ILD or non-infectious pneumonitis that required steroids
• Patients who have received a live vaccine within 30 days of the planned start of study therapy