This phase I trial studies the side effects of vaccine therapy and pembrolizumab in treating patients with solid tumors that have spread to other places in the body and usually cannot be cured or controlled with treatment, that have failed prior therapy, and that cannot be removed by surgery. Vaccines made from a gene-modified virus may help the body build an effective immune response to kill tumor cells. Monoclonal antibodies, such as pembrolizumab, may block tumor growth in different ways by targeting certain cells. Giving vaccine therapy together with pembrolizumab may be a better treatment in patients with solid tumors.

PRIMARY OBJECTIVES:

I. To determine the safety and tolerability of combined p53MVA vaccine (modified vaccinia virus Ankara vaccine expressing p53) and pembrolizumab that are well-tolerated in patients with refractory, tumor protein 53 (p53) over expressing cancer.

SECONDARY OBJECTIVES:

I. To evaluate clinical response and anti-p53 T cell immune responses.

OUTLINE: Patients receive pembrolizumab intravenously (IV) over 30 minutes followed by modified vaccinia virus Ankara vaccine expressing p53 subcutaneously (SC) at least 30 minutes later once in weeks 1, 4, and 7.

Patients may receive additional doses of pembrolizumab in weeks 10, 13, 16, and 19, for a maximum of 7 doses if there are no signs of progressive disease. Treatment continues in the absence of disease progression or unacceptable toxicity.

After completion of study treatment, patients are followed up periodically.

Inclusion Criteria:

• Since p53 mutations occur in a wide variety of tumor types, this is a mixed histology study for incurable tumors; subjects with the following solid tumors are eligible for screening: non-small cell lung cancer, squamous cell carcinoma of the head and neck, hepatocellular carcinoma, renal cell carcinoma, melanoma, bladder, soft tissue sarcoma, triple-negative breast cancer, and colorectal carcinoma displaying microsatellite instability and pancreatic cancer
• Advanced (unresectable) solid tumors: patients must have failed or been intolerant to at least one line of standard therapy or refuse standard treatment
• Performance status: patients must have an Eastern Cooperative Oncology Group (ECOG) =< 2 (Karnofsky >= 60%)
• Informed consent: all subjects must have the ability to understand and the willingness to sign an Institutional Review Board (IRB) approved consent form
• Absolute neutrophil count: >= 1,500/ul
• Platelets >= 100,000/ul
• Hemoglobin level: must be greater than 9 g/dL
• Renal function: calculated or measured creatinine clearance >= 50 ml/min and/or serum creatinine =< 1.6 mg/dl
• Total bilirubin =< 1.5 x institutional upper limit of normal
• Aspartate aminotransferase (AST) and alanine aminotransferase (ALT) =< 3 times institutional upper normal level (AST and ALT =< 5 times institutional upper normal level, if there is evidence of liver metastasis)
• Confirmed p53 involvement: patients with p53 over-expression by immunohistochemistry (>= 10% of cells within the tumor staining positive) or those with a p53 mutation as determined by mutational analysis of tumor tissue will be eligible; patients with prior exposure to p53-based vaccines will be eligible
• Agreement to use adequate contraception: women of child-bearing potential must use contraception prior to study entry and for six months after study participation; men that are sexually active whose partners are women of childbearing age must use condoms

Exclusion Criteria:

• Patients may not be receiving any additional investigational agents or radiation therapy
• Pregnancy: pregnant women are excluded from this study; should a woman become pregnant or suspect that she is pregnant while participating on the trial, she should inform her treating physician immediately; women who are pregnant or breastfeeding are excluded
• Patients with known brain metastasis
• Radiotherapy within 4 weeks prior to entering the study
• Patients with previous exposure to anti-programmed cell death (PD)-1 or anti-programmed cell death ligand 1 (PDL-1) will not be eligible
• History of allergy to egg proteins
• Patients who have not recovered from adverse events due to agents administered more than 4 weeks earlier
• Concurrent use of systemic corticosteroids (nasal corticosteroids, inhaled steroids, adrenal replacement steroids, and topical steroids are allowed)
• History of immunodeficiency or autoimmune disease: patients with a history of immunodeficiency, including organ grafts and human immunodeficiency virus (HIV), will not be eligible
• Patients with a history of autoimmune disease will also be excluded, specifically those with any active autoimmune disease or a condition that requires systemic corticosteroids; exceptions to this are subjects with vitiligo and type I diabetes mellitus, who will be permitted to enroll
• Patients with a history of severe immune-mediated adverse reactions with ipilimumab: this will be defined as any grade 4 toxicity requiring treatment with corticosteroids (greater than 10 mg/day prednisone or equivalent dose) for greater than 12 weeks
• Patients with a history of cardiac disease are excluded; baseline electrocardiography and assessment of serum troponin (I) are included the screening exams; subjects in whom these assays are abnormal (electrocardiogram [EKG] excluding 1st degree bundle branch block, sinus bradycardia, sinus tachycardia or non-specific T wave changes, serum troponin >= grade 2) are ineligible
• Non-compliance: if it is the opinion of the investigator that a subject may be unable to comply with the safety monitoring requirements of the study, they will be excluded