Inclusion Criteria:

- Patients must have documented malignant melanoma, American Joint Commission on Cancer
(AJCC) stage IIB, IIC, III or IV. Patients free of disease after surgical resection
will also be eligible.

- For all patients, pathology slides must be reviewed by the Memorial Hospital
Department of Pathology for confirmation of melanoma diagnosis.

- Patients must be HLA-A0201 positive.

- Patients must be at least 18 years of age to be eligible and must be able to read the
informed consent and give informed consent.

- Patients must have a Karnofsky performance status of at least 80.

- LDH < than or = to 2x upper limit of normal value; albumin > than or = to 3.5 mg/dl.

- A CBC prior to vaccination with WBC > or = to 3000, platelets > or = to 100,000.

- Patients must be free of detectable brain metastases.

Exclusion Criteria:

- Patients may not be receiving or have received chemotherapy, immunotherapy or
radiation therapy within the previous 4 weeks. Patients must be fully recovered from
any previous therapy or surgery.

- Patients may not have been previously immunized with vaccines containing tyrosinase
or peptides derived from tyrosinase.

- Any medical condition or use of medication (e.g., corticosteroids) which might make
it difficult for the patient to complete the full course of treatments or to respond
immunologically to vaccines is grounds for exclusion, at the discretion of the
Principal Investigator or co-Principal Investigators.

- Patients who have preexisting retinal or choroidal eye disease will be excluded.

- Patients with serious underlying medical conditions, active infections requiring
antimicrobial drugs, or active bleeding will be ineligible.

- Pregnant women or women who are less than 3 months post-partum are not eligible.
Women who may yet bear children and sexually active men must be using appropriate
contraception during the course of this study. Women of child-bearing potential must
not be pregnant (negative BHCG within 2 weeks of vaccination) nor be nursing during
treatment.