Inclusion Criteria:

- Stage IV melanoma according to the 2001 AJCC criteria. Limited tumor burden; LDH < 2x
upper limit of normal

- Histological proof of cutaneous melanoma

- Melanoma expressing tyrosinase and/or gp100 (approximately 20% of cells or more
determined by immunohistochemistry staining)

- HLA Type A2

- WBC > 3.0 * 10E9/l, lymphocytes > 0.8 * 10E9/l, platelets > 100 * 10E9/l, serum
creatinine < 150 umol/l, serum bilirubin < 25 umol/l, normal liver function

- Expected adequacy of follow up

- Written informed consent

Exclusion Criteria:

- autoimmune disorders, concomitant use of immunosuppressive drugs

- serious concomitant disease, serious active infections, other malignancy in the past
5 years with the exception of curatively treated carcinoma in-situ of the
cervix/squamous cell carcinoma of the skin

- known allergy to shell fish (vaccine contains KLH)

- pregnancy or lactation

- clinical signs of CNS metastases, in patients with a clinical suspicion of CNS
metastases, a CT scan of the brain should be performed to exclude this

- prior chemotherapy, immunotherapy, or radiotherapy within three months before planned
vaccination is allowed