Inclusion Criteria

DISEASE CHARACTERISTICS:

- Histologically confirmed melanoma

- Stage III (≥ 3 positive lymph nodes) or stage IV disease

- Mucosal or ocular melanoma allowed

- Completely resected within the past 6 months

- Patients with stage III resected melanoma rendered free of disease may have failed,
been ineligible for, or refused prior treatment with interferon alfa

- Positive staining of tumor tissue for at least one of the following:

- Antibody HMB-45 for gp100

- Antibody HMB-45 for tyrosinase

- Antibody HMB-45 for MART-1

- HLA-A*0201 positive by DNA allele-specific polymerase chain reaction assay

PATIENT CHARACTERISTICS:

Age

- 18 and over

Performance status

- ECOG 0-1

Life expectancy

- At least 6 months

Hematopoietic

- WBC ≥ 2,500/mm^3

- Absolute neutrophil count ≥ 1,500/mm^3

- Platelet count ≥ 100,000/mm^3

- Hematocrit ≥ 30%

- Hemoglobin ≥ 10 g/dL

Hepatic

- AST ≤ 3 times upper limit of normal (ULN)*

- Bilirubin ≤ ULN* (< 3.0 mg/dL for patients with Gilbert's syndrome)

- No significant hepatic disease that would preclude study participation

- Hepatitis B surface antigen negative

- Hepatitis C antibody negative NOTE: * Unless attributable to disease

Renal

- Creatinine ≤ 2.0 mg/dL

- No significant renal disease that would preclude study participation

Cardiovascular

- No significant cardiac disease that would preclude study participation

Pulmonary

- No significant pulmonary disease that would preclude study participation

Immunologic

- No history of any of the following:

- Inflammatory bowel disease or any other autoimmune bowel disease

- Systemic lupus erythematosus

- Rheumatoid arthritis

- Autoimmune ocular disease

- No systemic hypersensitivity to Montanide ISA-51 or any vaccine component

- No active infection requiring therapy

- HIV negative

Other

- No other malignancy within the past 5 years except adequately treated basal cell or
squamous cell skin cancer, superficial bladder cancer, or carcinoma in situ of the
cervix

- No significant gastrointestinal disease that would preclude study participation

- No significant psychiatric disease that would preclude study participation

- No other medical condition that would preclude study participation

- Not pregnant or nursing

- Negative pregnancy test

- Fertile patients must use effective contraception during and for at least 4 months
after study participation

PRIOR CONCURRENT THERAPY:

Biologic therapy

- See Disease Characteristics

- No prior anti-cytotoxic T-lymphocyte-associated antigen-4 monoclonal antibody
(MDX-010)

- No prior gp100 antigen, MART-1 antigen, or tyrosinase peptide

- At least 4 weeks since prior immunotherapy for melanoma and recovered

- No other concurrent immunotherapy

Chemotherapy

- At least 4 weeks since prior chemotherapy for melanoma (6 weeks for nitrosoureas) and
recovered

- No concurrent chemotherapy

Endocrine therapy

- At least 4 weeks since prior hormonal therapy for melanoma and recovered

- At least 4 weeks since prior systemic, inhaled, or topical corticosteroids

- No concurrent systemic, inhaled, or topical corticosteroids

Radiotherapy

- At least 4 weeks since prior radiotherapy for melanoma and recovered

Surgery

- See Disease Characteristics

- At least 4 weeks since prior surgery for melanoma and recovered

Other

- No concurrent immunosuppressive agents (e.g., cyclosporine and its analog)

- Concurrent analgesic therapy allowed provided the dose is stable for the past 14 days