Inclusion Criteria:

- Patients must have documented malignant melanoma, American Joint Commission on Cancer
(AJCC) stage IIB, IIC, III or IV (54). Patients with resectable stage IIB, IIC and
III disease must have undergone surgical resection before participating in this
study.

- Patients with choroidal melanoma may participate if they fulfill one of the following
criteria: Basal diameter > or = 16 mm; Height > or = 8 mm or involvement of ciliary
body with tumor.

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

- Patients must be HLA-A2 positive.

- Patients must weigh at least 25 kg to be eligible. Patients must be able to read the
consent form and give informed consent. Parent or legal guardians of patients who are
minors will sign the informed consent form.

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

- LDH ≤ 2x upper limit of normal value; albumin ≥ 3.5 mg/dl. Creatinine ≤ 2mg/dl and
AST ≤ 2- fold upper limit of normal.

- A CBC prior to vaccination with WBC ≥ 3000, platelets ≥ 100,000.

- A negative serum bHCG within 2 weeks of vaccination in women of childbearing age.

- Patients must be free of detectable brain metastases. (Brain MRI or CT pre-protocol)

Exclusion Criteria:

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

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

- Creatinine > 2mg/dl (or history of Creatinine > 2 mg/dl) and AST ≥ 2 fold upper limit
of normal.

- Any medical condition or use of medication (e.g., active autoimmune disease,
immunodeficiency or 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 may not have taken systemic corticosteroids
(orally or intravenously) within the previous 6 weeks. Inhaled or nasal steroids are
permitted.

- Patients who have preexisting retinal or choroidal eye disease (except as outlined in
section 5.1.1) will be excluded.

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

- Pregnant women, women who are less than 3 months post-partum or women who are nursing
are not eligible. Women of childbearing age and sexually active men must be using
appropriate contraception during the course of this study and for 3 months following
completion.