Inclusion Criteria:

- Patients who have been diagnosed, by cytologic or histologic examination, with AJCC
stage IIB, stage III or resected stage IV melanoma.

- Patients with up to 2 brain metastases less than or equal to 2 cm that have been
surgically removed or treated successfully with the gamma-knife are eligible.
Surgical resections must have been performed within 6 months prior to entry.

- All patients must have:

1. ECOG performance status 0-1, and,

2. Ability and willingness to give informed consent.

- Laboratory parameters as follows:

- HLA-A1, A2 or A3 (+)

- gp100 (+) and/or tyrosinase (+) tumor cells

- ANC > 1000/mm3, and Platelets > 100,000 and Hgb > 9

- Hepatic: AST and ALT up to 2.5 x upper limits of normal (ULN), Bilirubin up to
2.5 x ULN, Alkaline phosphatase up to 2.5 x ULN

- Renal: Creatinine up to 1.5 x ULN

- Serology: HIV negative, Hepatitis C negative

Exclusion criteria:

- Patients who are currently receiving cytotoxic Chemotherapy or radiation or who have
received that therapy within the preceding 4 weeks.

- Patients with known or suspected allergies to any component of the vaccine.

- Patients receiving the following medications at study entry or within the preceding
30 days are excluded:

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

- Allergy desensitization injections

- Corticosteroids, administered parenterally or orally - topical corticosteroids
are acceptable

- Any growth factors, Interleukin 2, Interferon alfa.

- Prior melanoma vaccinations will not be an exclusion criteria if given more than 8
weeks previously, but will be recorded, and data analysis will take this into
account.

- Other investigational drugs or investigational therapy also will not necessarily be
an exclusion criteria, but will similarly be recorded and taken into account during
data analysis.

- Pregnancy or the possibility of becoming pregnant during vaccine administration.

- Female patients of child-bearing potential must have a negative pregnancy test
(urinary or serum beta-HCG) prior to administration of the first vaccine dose.

- Males and females must agree, in the consent form, to use effective birth
control methods during the course of vaccination.

- This is consistent with existing standards of practice for vaccine and
chemotherapy protocols.

- Patients in whom there is a medical contraindication or potential problem in
complying with the requirements of the protocol, in the opinion of the investigator.

- Patients classified according to the New York Heart Association classification system
as having Class II, III or IV heart disease.

- Patients with active connective tissue disease requiring medication, or other severe
autoimmune disease.

- Patients who are actively hyperthyroid.

- Patients with uncontrolled diabetes.