Multiple Class I Peptides & Montanide ISA 51 VG w Escalating Doses of Anti-PD-1 ab BMS936558

Inclusion Criteria:

* Histologic diagnosis of unresectable Stage III or IV melanoma. All melanomas regardless of primary site of disease will be allowed
* Measurable unresectable melanoma at least 1 measurable lesion based on Immune-related Response Criteria (irRC)
* Have failed at least 1 chemotherapy regimen for metastatic disease, and have been treated with up to 2 prior chemotherapy regimens
* HLA-A\*0201 positive as determined by deoxyribonucleic (DNA) allele-specific polymerase chain reaction (PCR) assay; for cohort 5 after amendment 9 and cohort 6, there is no HLA restriction
* Positive staining of tumor tissue with antibodies to 1 or more of the following: human melanoma black 45 (HMB 45) for gp100, NY-ESO-1, and/or MART-1
* Eastern Cooperative Oncology Group (ECOG) performance status score of 0 or 1
* Prior chemotherapy or immunotherapy must have been completed at least 4 weeks before study drug administration, and all adverse events have either returned to baseline or stabilized
* Prior treated brain or meningeal metastases must be without magnetic resonance imaging (MRI) evidence of progression for at least 8 weeks and off immunosuppressive doses of systemic steroids (\> 10 mg/day prednisone or equivalent) for at least 2 weeks before study drug administration
* Prior systemic radiation therapy must have been completed at least 4 weeks before study drug administration. Prior focal radiotherapy completed at least 2 weeks before study drug administration. No radiopharmaceuticals (strontium, samarium) within 8 weeks before study drug administration
* Immunosuppressive doses of systemic medications, such as steroids or absorbed topical steroids (doses \> 10 mg/day prednisone or equivalent) must be discontinued at least 2 weeks before study drug administration
* Completed nitrosourea treatment at least 6 weeks before administration of any study drug
* Prior surgery that required general anesthesia must be completed at least 2 weeks before study drug administration. Surgery requiring local/epidural anesthesia must be completed at least 72 hours before study drug administration and patients should be recovered.
* Screening laboratory values must meet the following criteria:

  * white blood cells (WBCs) ≥ 2000 cells/ µL
  * neutrophils ≥ 1500 cells/ µL
  * platelets ≥ 100 x 10\^3/ µL
  * hemoglobin ≥ 9.0 g/dL
  * serum creatinine ≤ 2 mg/dL
  * aspartic transaminase (AST) ≤ 2.5 x upper limit of normal (ULN) without, and ≤ 5 x ULN with hepatic metastasis
  * alanine transaminase (ALT) ≤ 2.5 x ULN without, and ≤ 5 x ULN with hepatic metastasis
  * bilirubin ≤ 2 x ULN (except patients with Gilbert's syndrome, who must have total bilirubin \< 3.0 mg/dL)
* Females of childbearing potential must: Agree to use using a reliable form of contraception (eg, oral contraceptives, intrauterine device, double barrier method of condom and spermicidal) for at least 28 days prior to the first dose of any study drug, during the Treatment Period (and Treatment/Follow-up if receiving study drug), and for at least 70 days after the last dose of any study drug; have a negative serum β-human chorionic gonadotropin (β-HCG) at Screening.
* Males must agree to the use of male contraception during the Treatment Period and for at least 180 days after the last dose of any study drug.
* Must have read, understood, and provided written informed consent and Health Insurance Portability and Accountability Act (HIPAA) authorization after the nature of the study has been fully explained
* Willing to adhere to the study visit schedule and the prohibitions and restrictions specified in this protocol

Exclusion Criteria:

* History of severe hypersensitivity reactions to other monoclonal antibodies (mAbs)
* Systemic hypersensitivity to Montanide ISA 51 VG or any vaccine component
* Prior malignancy active within the previous 2 years except for locally curable cancers that have been apparently cured, such as basal or squamous cell skin cancer, superficial bladder cancer, or carcinoma in situ of the prostate, cervix or breast
* Patients with any active autoimmune disease or a documented history of autoimmune disease, or history of syndrome that required systemic steroids or immunosuppressive medications, except for patients with vitiligo or resolved childhood asthma/atopy
* Known history of testing positive for human immunodeficiency virus (HIV) or known acquired immunodeficiency syndrome (AIDS)
* Positive tests for hepatitis B virus surface antigen (HBV SAg) or hepatitis C virus ribonucleic acid (HCV RNA) indicating active or chronic infection
* Prior therapy with an anti-PD-1, anti-PD-L1, anti-programmed death-ligand-2 (PDL-2), or anti-cytotoxic T lymphocyte-associated antigen 4 (CTLA-4) antibody (or any other antibody targeting T cell co-stimulation pathways)
* Concurrent medical condition requiring the use of immunosuppressive medications, or immunosuppressive doses of systemic or absorbable topical corticosteroids
* Underlying medical condition (eg, a condition associated with diarrhea) that, in the Investigator's opinion, would make the administration of either study drug or both study drugs hazardous to the patient or obscure the interpretation of toxicity determination or adverse events
* Pregnant or nursing
* Current participation in another clinical study involving treatment with medications, radiation or surgery, or prior participation in this study