Inclusion Criteria

Inclusion Criteria

- This study is confined to adults over the age of 18 with histologically proven
malignant melanoma.

- MART-1, as assessed by either RT-PCR or by immunohistochemistry.

- Subjects must be typed for HLA-A*0201 for the phase I part of the study, and
HLA-A*0201 and/or DR*04 for the phase II part.

- Stage with unresectable measurable melanoma (stage IV or stage III unresectable).
Patients previously treated with any form of therapy (including chemotherapy,
radiation therapy, immunotherapy or surgery) for either metastatic, relapsed or
primary melanoma are eligible for this trial, provided that previous the previous
treatment was completed > 30 days prior to first vaccine.

- Both male and female patients may be enrolled. Premenopausal females must have a
negative pregnancy test prior to treatment.

- Karnofsky Performance Status greater than or equal to 70 percent, or ECOG greater
than 2.

- No previous evidence of class 3 or greater New York Heart Association cardiac
insufficiency or coronary artery disease.

- No previous evidence of opportunistic infection.

- A minimum of 30 days must have elapsed since the completion of prior chemotherapy,
immunotherapy or radiation therapy.

- Adequate baseline hematological function as assessed by the following laboratory
values within 30 days prior to study entry:

- Hemoglobin > 9.0 g/dl.

- Platelets > 100,000/mm3.

- WBC > 3,000/mm3.

- Absolute Neutrophil Count (ANC) > 1,000/mm3.

- Ability to give informed consent.

Exclusion Criteria

Patients who meet any one of the following criteria will be excluded from study entry:

- Lactating females: Females of child-bearing potential (pre-menopausal) must have a
negative serum beta-HCG pregnancy test (within Day -7 to Day 0).

- Acute infection: any acute viral, bacterial, or fungal infection which requires
specific therapy. Acute therapy must have been completed within 14 days prior to
study treatment.

- HIV-infected patients, due to concerns in the ability to stimulate an effective
immune response.

- Acute medical problems such as ischemic heart or lung disease that may be considered
an unacceptable anesthetic or operative risk.

- Patients with any underlying conditions which would contraindicate therapy with study
treatment (or allergies to reagents ).

- Patients with organ allografts.

- Uncontrolled CNS metastasis. Patients with CNS metastasis will be eligible if they
have received CNS irradiation to control local tumor growth.

- Previous clinical evidence of an autoimmune disease.

- Concomitant Medication and Treatment

All allowed medications or treatments should be kept to a minimum and recorded. All
questions regarding concomitant medications should be referred to the study chair or
investigator.

Medications and Treatments Not Allowed

- Corticosteroids

- Chemotherapy

- Cyclosporin A.