Inclusion Criteria:

1. Histologically proven cutaneous melanoma, or clear cell sarcoma, which is considered
as a subtype of melanoma.

2. Melanoma must be at one of the following AJCC 2002 stages:

- Regional metastatic disease (any T; N2b, N2c or N3; M0).

- Distant metastatic disease (any T; any N; M1a, M1b or M1c), except brain or
leptomeningeal localizations, and except elevated LDH.

3. Patients must be HLA-A1.

4. Melanoma must express the MAGE-3 gene, as determined by RT-PCR.

5. Presence of at least one measurable or non-measurable tumor lesion, excluding
leptomeningeal metastasis (see Section 7.3).

6. Expected survival of at least 3 months.

7. Karnofsky performance scale ≥70 or WHO performance status of 0 or 1.

8. Within the last 4 weeks prior to study day 1, vital laboratory parameters should be
within normal range, except for the following laboratory parameters, which must be
within the ranges specified:

Lab Parameter Range

- Hemoglobin ≥ 10 g/dl or ≥ 6,25 mmol/l

- Granulocytes ≥ 1,500/µl

- Lymphocytes ≥ 700/µl

- Platelets ≥ 100,000/µl

- Serum creatinin ≤ 2.0 mg/dl or ≤ 177 mmol/l

- Serum bilirubin ≤ 2.0 mg/dl or ≤ 34.2 mmol/l

- ASAT and ALAT ≤ 2 x the normal upper limits

- LDH ≤ the normal upper limit.

9. Viral tests:

- HIV (human immunodeficiency virus): negative antibodies.

- HBV (hepatitis B virus): negative antigens; antibodies may be positive.

- HCV (hepatitis C virus): negative antibodies.

10. Age ≥ 18 years

11. Able and willing to give valid written informed consent.

Exclusion Criteria:

1. Previous treatment with more than one regimen of systemic chemotherapy, combined or
not with non-specific immunotherapy such as interferon alpha or interleukins.
Chemoimmunotherapy or radiotherapy must be stopped within the preceding 4 weeks (6
weeks for nitrosoureas and mitomycin C).

2. Previous treatment with a vaccine known or likely to contain the MAGE-3.A1 antigen,
unless there is evidence that no CTL response against this antigen was induced by the
vaccine.

3. Clinically significant heart disease (NYHA Class III or IV) i.e. NYHA class 3
congestive heart failure; myocardial infarction within the past six months; unstable
angina; coronary angioplasty within the past 6 months; uncontrolled atrial or
ventricular cardiac arrhythmias).

4. Active immunodeficiency or autoimmune disease. Vitiligo is not an exclusion
criterion.

5. Other serious acute or chronic illnesses, e.g. active infections requiring
antibiotics, bleeding disorders, or other conditions requiring concurrent medications
not allowed during this study.

6. Other malignancy within 3 years prior to entry into the study, except for treated
non-melanoma skin cancer and cervical carcinoma in situ.

7. Lack of availability for immunological and clinical follow-up assessments.

8. Participation in any other clinical trial involving another investigational agent
within 4 weeks prior to enrollment.

9. Pregnancy or breastfeeding.

10. Women of childbearing potential: Refusal or inability to use effective means of
contraception.