Inclusion Criteria:

1. Participants with stage IIIB, IIIC or IV melanoma with cutaneous metastases.

2. Patients must have adequate cutaneous metastases of melanoma readily accessible for
biopsy to provide a minimum of 0.3 cm3 of tissue per biopsy (approximately 0.85 cm by
0.85 cm x 0.85 cm or five 2mm core biopsies) at each of three time points. Several
scenarios may fulfill the tumor burden requirement. For example, a patient may have
one large lesion from which core biopsies can be taken for the first and second
biopsy time points and then the entire lesion excised for the final tissue sample.
Other combinations are acceptable.

3. The intent is to limit this study to patients with cutaneous melanoma metastasis
rather than subcutaneous or lymph node metastasis because imiquimod may not penetrate
to those deeper metastases.

4. Patients may have had multiple primary melanomas.

5. Patients may have had or may have a metastasis from a cutaneous primary site, mucosal
primary site, ocular primary site, or unknown primary site.

6. Patients who have had brain metastases may be eligible if they meet the following
criteria

- Patients with less than or equal to 5 metastases may be eligible as long as the
following 3 criteria are true:

- The brain metastases have been completely removed by surgery or have been
treated completely by stereotactic radiotherapy. Stereotactic radiotherapy,
such as gamma knife, can be used up to 1 week prior to study entry.

- There has been no evident growth of any brain metastasis since treatment.

- No metastasis greater than 2 cm at the time of protocol entry

- Patients with greater than 5 metastases may be eligible if the above 3 criteria
are met and if at least one year has elapsed since the last treatment.

7. All participants must have ECOG performance status of 0 or 1 and ability and
willingness to give informed consent

8. Patients must have at least one intact axillary and/or inguinal lymph node basin. A
patient with a prior lymph node biopsy may be a candidate if lymphoscintigraphy
demonstrates intact drainage to a node in that basin. A lymphoscintigram may be
performed during screening to ensure that there is drainage to a regional node from a
planned vaccine site. If the lymphoscintigram is performed and a sentinel lymph node
is not located, the patient will be ineligible for this study if no other vaccine
sites are available.

9. Laboratory parameters as follows: The following laboratory parameters will be
required for all participants. If a lab value appears to be an error or a result of
a transient or treatable condition, the investigator will use his/her clinical
judgment to decide if the test may be repeated. The requirements for inclusion are
as follows:

- HLA-A1, -A2, -A3, or -A11+

- ANC > 1000/mm3

- Platelets > 100,000/mm3

- Hgb ≥ 9 g/dL

- HGBA1C < 7%

- AST and ALT ≤ 2.5 x upper limits of normal (ULN)

- Bilirubin ≤ 2.5 x ULN

- Alkaline phosphatase ≤ 2.5 x ULN

- Creatinine ≤ 1.5 x ULN

- HIV negative (within 6 months of study entry)

- Hepatitis C negative (within 6 months of study entry)

- LDH up to 2 x ULN

10. Patients must be 18 years or older at study entry

Exclusion Criteria:

1. Patients who have had brain metastases unless they meet the criteria outlined above

2. Patients who are currently receiving systemic cytotoxic chemotherapy, radiation, or
other experimental therapy, or who have received this therapy within the preceding 4
weeks. Gamma knife or stereotactic radiosurgery may be administered within the prior
4 weeks, but must not be administered less than one week prior to study enrollment.
Patients who are currently receiving nitrosoureas or who have received this therapy
within the preceding 6 weeks.

3. Patients will not be eligible if there is clinically detectable melanoma deemed
likely by the investigator to require intervention during the first 12 weeks of the
study that would require premature discontinuation. Examples for such circumstances
may include untreated bone metastases at risk for fracture, and rapidly progressive
low volume disease.

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

5. Patients receiving the following medications at study entry or within the preceding 4
weeks are excluded:

- Agents with putative immunomodulating activity (with the exception of
non-steroidal anti-inflammatory agents and topical steroids

- Allergy desensitization injections.

- Systemic corticosteroids, administered parenterally or orally. Inhaled steroids
(e.g. Advair®, Flovent®, Azmacort®) are not permitted. Topical corticosteroids
are acceptable, including steroids with very low solubility administered nasally
for local effects only (e.g. Nasonex®).

- Any pharmacologic growth factors (e.g. GM-CSF, G-CSF, erythropoietin).

- Interferon therapy.

- Interleukin-2 or other interleukins.

- Topical 5% Imiquimod cream: Patients must not have had imiquimod therapy to any
body site within 4 weeks of study entry and must not have had any prior
imiquimod therapy to the lesions to be treated, watched or biopsied on this
present study. If imiquimod has been used in the past and either led to
complete regression of the treated lesions, or those lesions have been removed
surgically, then the patient may be eligible.

6. Prior melanoma vaccinations may be an exclusion criterion in som circumstances:

- Patients who have recurred or progressed either after or during administration
of a melanoma vaccine may be eligible to enroll 12 weeks following their last
vaccination.

- Patients may have been vaccinated previously with peptide vaccines (including
MELITAC 12.1 and similar vaccines) or with non-peptide vaccines.

7. 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. Women must also not be breast feeding. This is
consistent with existing standards of practice for vaccine and chemotherapy
protocols.

8. 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.

9. Patients classified according to the New York Heart Association classification as
having Class III or IV heart disease (Appendix 4).

10. Patients with a body weight < 110 lbs because of the amount and frequency with which
blood will be drawn

11. Participants must not have had prior autoimmune disorders requiring cytotoxic or
immunosuppressive therapy, or autoimmune disorders with visceral involvement.
Participants with an active autoimmune disorder requiring these therapies are also
excluded. The following will not be exclusionary:

- The presence of laboratory evidence of autoimmune disease (e.g. positive ANA
titer) without associated symptoms

- Clinical evidence of vitiligo

- Other forms of depigmenting illness

- Mild arthritis requiring NSAID medications or no medical therapy