This pilot phase II trial studies how well giving vaccine therapy works in treating patients with stage IIC-IV melanoma. Vaccines made from melanoma peptides or antigens may help the body build an effective immune response to kill tumor cells

PRIMARY OBJECTIVES I. To perform a two-cohort, two-stage phase II two cohort pilot trial of a multi-peptide melanoma vaccine (multi-epitope melanoma peptide vaccine) with Montanide ISA 51 (incomplete Freund's adjuvant) or ISA 51 VG (Montanide ISA 51 VG) with adjuvant 7909 (agatolimod sodium) to define the safety and tolerability of each of the regimens, and to evaluate immune reactivity to a tyrosinase/gp100/MAGE-3 class I peptide vaccine combined with Montanide ISA 51 or ISA 51 VG with CpG adjuvant 7909 in human leukocyte antigen (HLA) class I A1, A3 or A11 and B44 matched patients with surgically resected stages IIC, III and IV melanoma.

OUTLINE: Patients are assigned to 1 of 2 treatment cohorts.

COHORT I: Patients receive multi-epitope peptide melanoma peptide vaccine with incomplete Freund's adjuvant and agatolimod sodium subcutaneously (SC) at 0, 2, 4, 6, 8, 10, 14, 18, 22, 26, 38, and 50 weeks and then every six months for two years for up to 16 vaccinations in the absence of disease progression or unacceptable toxicity.

COHORT II: Patients receive multi-epitope peptide melanoma peptide vaccine with Montanide ISA 51 VG and agatolimod sodium SC at 0, 2, 4, 6, 8, 10, 14, 18, 22, 26, 38, and 50 weeks and then every six months for two years for up to 16 vaccinations in the absence of disease progression or unacceptable toxicity.

After completion of study treatment, patients are followed up every 6 months for 3 years, and then annually thereafter.

Inclusion Criteria:

• Stages IIC, III and IV cutaneous, or mucosal melanoma or stages III/IV ocular melanoma that have been completely resected; those rendered disease-free by radiation or systemic chemotherapy and/or immune therapy will also be eligible; patients must be entered within 12 months of disease-free status
• Patients must be positive for at least one of human leukocyte antigen (HLA) A1, A3/A11 typed by a standard deoxyribonucleic acid (DNA)-polymerase chain reaction (PCR) assay, and HLA-B44 status must be known; patients who are B44 positive but do not express A1, A3 or A11 are not eligible for this trial
• Tumor tissue must be available for analysis of gp100 and tyrosinase expression by immunohistochemistry; positive staining for at least one antigen will be an eligibility criteria for this trial
• Serum creatinine of 2.0 mg/dl or less
• Total bilirubin of 2.0 mg/dl or less
• Serum glutamic oxaloacetic transaminase (SGOT)/serum glutamate pyruvate transaminase (SGPT) of 2.5 X institutional norm or less
• Total white blood cell (WBC) of 3,000 or more
• At least 1500 granulocytes
• Hemoglobin of 9.0 gm/dl
• Platelet count of 100,000 per cu mm
• Eastern Cooperative Oncology Group (ECOG) performance status of 0 or 1
• Patients will be eligible for this trial if they have failed alpha-interferon, if it is felt to be contraindicated due to a pre-existing medical or psychiatric condition or if they have refused treatment with it
• Ability to read, understand and willingness to sign an institutional review board (IRB)-approved informed consent

Exclusion Criteria:

• Who are undergoing or have undergone in the past month any other therapy for their cancer, including radiation therapy and adjuvant therapy; six weeks must have elapsed for nitrosoureas
• Have major systemic infections like pneumonia or sepsis, coagulation or bleeding disorders, or other major medical illnesses of the gastrointestinal, cardiovascular or respiratory systems
• Who require steroid therapy or have been treated with steroids within 4 weeks of starting the trial
• Who are pregnant or lactating, since the risk of autoimmune reactivity to tyrosinase or gp100 is felt to present a risk to the fetus or a breast feeding infant
• Who are known to be positive for hepatitis B surface antigen (BsAg), Hepatitis C antibody or human immunodeficiency virus (HIV) antibody; since cells removed for ex vivo handling and tissue culture cannot be virus positive, and the effects of 7909 might be detrimental to HIV positive patients, patients positive for the above viruses will not be treated on this trial
• Who have had a known allergic reaction to Montanide ISA 51 or ISA 51 VG
• Who have a prior history of uveitis, autoimmune inflammatory eye disease or other autoimmune diseases other than vitiligo or controlled thyroiditis
• Who have had another malignancy within the last three years with the exception of squamous or basal carcinoma of the skin or carcinoma in situ of the cervix that have been treated with curative intent
• Who have previously received any of the peptides in the vaccine