Inclusion Criteria

DISEASE CHARACTERISTICS:

- Histologically or cytologically confirmed melanoma that meets one of the following
criteria:

- Stage IIB-IV melanoma rendered clinically free of disease by surgery, other
therapy, or spontaneous remission within the past 6 months

- Stage III or IV melanoma with disease

- Persistent or metastatic disease allowed if RECIST criteria for measurable disease is
not met

- Multiple primary melanomas allowed

- Prior or concurrent metastasis from a cutaneous, mucosal, ocular, or unknown primary
site allowed

- No clinically detectable melanoma deemed likely by the investigator to require
intervention during the first 12 weeks of the study that would require premature
discontinuation (e.g., untreated bone metastases at risk for fracture or rapidly
progressive low-volume disease)

- Brain metastases allowed if all of the following criteria are met:

- The total number of brain metastases ever is ≤ 3

- The brain metastases have been completely removed by surgery or have been
treated completely by stereotactic radiotherapy

- There has been no evident growth of any brain metastasis since treatment

- No treated brain metastasis > 2 cm in diameter

- At least two intact axillary and/or inguinal lymph node basins

- Prior lymph node biopsy allowed if lymphoscintigraphy demonstrates intact drainage to
a node in that basin

- If a sentinal lymph node is not located by lymphoscintigraphy, patient is not
eligible for study

- HLA-A1, -A2, -A3, or -A11 positive

- Either eligible for, but refused interferon therapy OR not a candidate for interferon
therapy for the following reasons:

- Active ischemic heart disease or cerebrovascular disease

- Anginal syndrome requiring ongoing medications or history of myocardial
infarction or arrhythmia disorder

- History of treatment for depression, active depression, or other psychiatric
disorder

- Autoimmune disorders

- Hypersensitivity to interferon-alfa or any component associated with interferon
therapy

- Debilitating medical conditions such as severe pulmonary disease or severe
diabetes mellitus

- Thyroid abnormalities, where thyroid function cannot be maintained in the normal
range without medication

- Resected stage IV melanoma

- Discontinued interferon therapy due to the occurrence of a major toxicity that
has been documented by the treating physician

- Experienced tumor progression while on interferon or after completing interferon
therapy

- Missed the standard-of-care enrollment window for interferon therapy initiation

PATIENT CHARACTERISTICS:

- ECOG performance status 0-1

- ANC > 1,000/mm^3

- Platelets > 100,000/mm^3

- Hemoglobin > 9 g/dL

- AST and ALT ≤ 2.5 times upper limit of normal (ULN)

- Bilirubin ≤ 2.5 times ULN

- Alkaline phosphatase ≤ 2.5 times ULN

- Creatinine ≤ 1.5 times ULN

- Hepatitis C and HIV negative (antibody screening)

- Hemoglobin_A1C level < 7%

- Body weight ≥ 110 pounds

- Not pregnant or nursing

- Negative pregnancy test

- Fertile patients must use effective contraception during study treatment

- No New York Heart Association class III-IV heart disease

- No known or suspected allergies to any component of the vaccine

- No medical contraindication or potential problem in complying with the requirements
of the protocol

PRIOR CONCURRENT THERAPY:

- See Disease Characteristics

- Prior peptide vaccines (including MELITAC 12.1 and similar vaccines) or non-peptide
vaccines allowed

- At least 1 week since prior stereotactic radiotherapy, such as gamma knife

- No influenza vaccine ≥ 2 weeks before, during, and ≥ 2 weeks after completion of
study therapy

- More than 4 weeks since prior and no concurrent use of any of the following:

- Systemic cytotoxic chemotherapy (6 weeks for nitrosoureas)

- Radiotherapy

- Other experimental therapy

- Agents with putative immunomodulating activity (with the exception of
non-steroidal anti-inflammatory agents and topical steroids)

- Allergy desensitization injections

- Systemic corticosteroids, administered parenterally or orally

- Inhaled steroids (e.g., fluticasone propionate [Advair® or Flovent®] or
triamcinolone acetonide [Azmacort®])

- Topical corticosteroids and steroids with very low solubility administered
nasally for local effects only allowed (e.g., mometasone furoate
[Nasonex®])

- Growth factors (e.g., sargramostim [GM-CSF], filgrastim [G-CSF], or epoetin
alfa)

- Interferon therapy

- Aldesleukin or other interleukins

- Street drugs

- At least 1 month since prior and no other concurrent investigational drugs or therapy

- At least 12 weeks since prior melanoma vaccine for patients who have recurred or
progressed either after or during treatment with vaccine