Inclusion Criteria:

- Histologically or cytologically proven melanoma that meets one of the following two
criteria:

- Stage IIB-IV melanoma rendered clinically free of disease by surgery, other
therapy, or spontaneous remission within 6 months prior to registration.

- Stage III or IV melanoma with disease. Patients may be eligible if there are
definite or equivocal findings of persistent or metastatic disease as long as
those findings do not meet RECIST criteria for measurable disease.

- Patients with brain metastases may be eligible if all of the following are true:

- The total number of brain metastases ever is less than or equal to 3.

- 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 treated brain metastasis is greater than 2 cm in diameter at the time of
protocol entry.

- Patients must have at least two intact axillary and/or inguinal lymph node basins.

- All patients must have:

- ECOG performance status of 0 or 1.

- Ability and willingness to give informed consent.

- Laboratory parameters as follows:

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

- ANC > 1000/mm3

- Platelets > 100,000/mm3

- Hgb ≥ 9 g/dL

- 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

- Hepatitis C negative

- HGBA1C level of < 7%

Exclusion Criteria:

- Patients who have had brain metastases, unless they meet inclusion criteria

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

- Patients with clinically detectable melanoma deemed likely by the investigator to
require intervention during the first 12 weeks of the study that would require
premature discontinuation.

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

- 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 growth factors (e.g. GM-CSF, G-CSF, erythropoietin).

- Interferon therapy.

- Interleukin-2 or other interleukins.

- Toll-like receptor agonists, including imiquimod or resiquimod.

- Prior melanoma vaccinations may be an exclusion criterion in some 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 (except that
they may not have been vaccinated with peptides included in MELITAC 12.1 or
MELITAC 12.6)

- Patients may have been vaccinated with protein, DNA, or cell-based vaccines that
include the proteins from which these peptides are derived.

- Other investigational drugs or investigational therapy if the patient is currently
taking those drugs/therapy, or if they have received the drugs/therapy within 1
month.

- Pregnancy or the possibility of becoming pregnant during vaccine administration.
Women must also not be breast feeding.

- 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 as having Class III or IV heart disease according to the New York
Heart Association

- Body weight < 110 lbs

- No active or prior autoimmune disorders requiring cytotoxic or immunosuppressive
therapy, or autoimmune disorders with visceral involvement. 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