This study evaluates whether it is safe to administer a peptide vaccine in combination with pembrolizumab. This study will also evaluate the effects of the combination of the peptide vaccine and pembrolizumab on the immune system. The investigators will monitor these effects by performing tests in the laboratory on participants' blood, a lymph node, and tumor samples.

Inclusion Criteria:

1. Subjects with unresectable American Joint Committee on Cancer (AJCC) stage IIIB or stage IIIC melanoma, or stage IV metastatic melanoma that have clinical or radiological evidence of disease. Subjects may have had cutaneous, uveal, mucosal primary melanoma, or an unknown primary melanoma. Staging must be confirmed by cytological or histological examination. Staging of cutaneous melanoma will be based on the revised AJCC staging system

2. Ability to provide written informed consent/assent for the trial.

3. ≥18 years of age

4. A subject may be naïve for immunotherapy agents or have received interferon-alpha, ipilimumab or other cytotoxic T lymphocyte antigen (CTLA)-4 antibody, Programmed death-1 (PD-1) antibody (or anti-PD-L1 antibody), interleukin-2, or prior cancer vaccines other than the 6MHP vaccine. Patients who have received a PD-1/PD-L1 antibody may be enrolled in either of the following settings:

   1. A patient who has experienced progression of melanoma during that therapy or after having completed that therapy,
   2. A patient who fails to experience an objective clinical response (partial response or complete response by RECIST 1.1 criteria) after either 12 weeks of continuous anti-PD1 antibody or anti-CTLA4/anti-PD1 combination therapy, and is a candidate to receive pembrolizumab therapy

5. Measurable disease based on RECIST 1.1.

   Subjects will be required to have radiological studies to define radiologically evident disease. Required studies include:

   • Chest CT scan,
   • Abdominal and pelvic CT scan, and
   • Head CT scan or MRI Positron emission tomography (PET)/CT fusion scan may replace scans of the chest, abdomen, and pelvis.

6. Subjects who have metastatic melanoma available for biopsy pretreatment and on day 22 must consent to having those biopsies. These metastases may be in nodes, skin, soft tissue, liver, or other sites that can be accessed safely by needle biopsy, incisional or excisional biopsy, with or without image guidance. The lesions to be biopsied must be specified at study enrollment and not included as target lesions for RECIST calculations. In instances where disease that is accessible to biopsy is limited, archival tissue specimens collected after a subject's last systemic therapy may be used for baseline measures.

   Subjects must have measurable disease in addition to the lesion(s) to be biopsied.

7. Subjects who have had brain metastases will be eligible if all of the following are true:

   • Each brain metastasis must have been completely removed by surgery or each unresected brain metastasis must have been treated with stereotactic radiosurgery.
   • There has been no evident growth of any brain metastasis since the most recent treatment
   • No brain metastasis is > 2 cm in diameter at the time of registration.
   • Neurologic symptoms have returned to baseline,
   • There is no evidence of new or enlarging brain metastases,
   • Subjects are not using steroids for at least 7 days prior to registration.

8. The most recent surgical resections or gamma-knife therapy for malignant melanoma must have been completed ≥ 1 week prior to registration.

9. Eastern Cooperative Oncology Group (ECOG) performance status of 0 or 1

10. Adequate organ function.

11. Two intact (undissected) axillary and/or inguinal lymph node basins.

Exclusion Criteria

1. Is currently participating in or has participated in a study of an investigational agent or using an investigational device within 4 weeks of the first dose of treatment.

2. Is currently receiving Interferon (e.g. Intron-A®), growth factors (e.g. Procrit®, Aranesp®, Neulasta®), or interleukins (e.g. Proleukin®), or has received these agents within 4 weeks of the first dose of treatment.

3. Is currently receiving nitrosureas or has received this therapy within the preceding 6 weeks of first dose of treatment.

4. Has a diagnosis of immunodeficiency or is receiving systemic steroid therapy or any other form of immunosuppressive therapy within 7 days prior to the first dose of trial treatment with the following exceptions (which are permitted):

   • replacement steroid doses in patients with adrenal or pituitary insufficiency
   • Intra-articular steroid injections
   • Inhaled steroids (e.g.: Advair®, Flovent®, Azmacort®) at low doses (less than 500 mcg fluticasone per day, or equivalent)
   • Topical and nasal corticosteroids
   • Non-steroidal anti-inflammatory drugs

5. Has had a prior monoclonal antibody within 4 weeks prior to study Day 1 or who has not recovered (i.e. ≤ Grade 1 or at baseline) from adverse events due to agents administered more than 4 weeks earlier.

6. Has had prior chemotherapy, targeted small molecule therapy, or external beam radiation therapy within 2 weeks prior to study Day 1 or who has not recovered (i.e., ≤ Grade 1 or at baseline) from adverse events due to a previously administered agent.

   • Note: Subjects with ≤ Grade 2 neuropathy are an exception to this criterion and may qualify for the study.
   • Note: If subject received major surgery, they must have recovered adequately from the toxicity and/or complications from the intervention prior to starting therapy.

7. Has a known additional malignancy that is progressing or requires active treatment. Exceptions include carcinoma in situ of the breast (DCIS or LCIS), basal cell carcinoma of the skin, squamous cell carcinoma of the skin, or in situ cervical cancer that has undergone potentially curative therapy.

8. Has known active central nervous system (CNS) metastases and/or carcinomatous meningitis.

9. Has 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 or immunosuppressive agents. Exceptions to this criterion include:

   • Subjects with vitiligo or other depigmenting illness.
   • Resolved childhood asthma/atopy
   • Intermittent use of bronchodilators or local steroid injections
   • Hypothyroidism stable on hormone replacement or Sjogren's syndrome
   • The presence of laboratory evidence of autoimmune disease (e.g. positive ANA titer) without symptoms
   • Mild arthritis requiring NSAID medications

10. Has evidence of interstitial lung disease or active, non-infectious pneumonitis.

11. Has an active infection requiring systemic therapy.

12. Has a history or current evidence of any condition, therapy, or laboratory abnormality that might confound the results of the trial, interfere with the subject's participation for the full duration of the trial, or is not in the best interest of the subject to participate, in the opinion of the treating investigator.

13. Has known psychiatric or substance abuse disorders that would interfere with cooperation with the requirements of the trial.

14. Is pregnant or breastfeeding, or expecting to conceive or father children within the projected duration of the trial, starting with the pre-screening or screening visit through 120 days after the last dose of trial treatment.

15. Is HIV positive or has evidence of active Hepatitis C virus (testing to be done within 6 months of study entry) or active Hepatitis B virus.

16. Has received a live vaccine or allergy desensitization injections within 30 days prior to the first dose of trial treatment.

17. Has known or suspected allergies to any component of the vaccine.

18. Has been vaccinated previously with any of the synthetic peptides included in this protocol.

19. Is classified according to the New York Heart Association classification as having Class III or IV heart disease (Appendix 12.5).

20. Has uncontrolled diabetes, defined as having a HGBA1C > 7.5%.

21. Has a body weight < 110 pounds (without clothes) at enrollment, due to the amount and frequency with which blood will be drawn.

Adverse events and dose-limiting toxicities (DLTs) were monitored up to 30 days after the last study treatment.