Inclusion Criteria:

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

- For Arms A and B: Stage IIIB-IV melanoma rendered clinically free of disease by
surgery, other therapy, or spontaneous remission

- For Arm C: Stage IIA-IV melanoma rendered clinically free of disease by surgery,
other therapy, or spontaneous remission

- For all Arms: 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 may have had one or more prior therapies for melanoma.

- Patients may have had multiple primary melanomas.

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

- All participants must have:

- ECOG performance status of 0 or 1

- Ability and willingness to give informed consent

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

- 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-A2+

- ANC > 1000/mm3

- Platelets > 100,000/mm3

- Hgb ≥ 9 g/dL

- HGBA1C < 7%

- Hepatic:

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

- Bilirubin ≤ 2.5 x ULN

- Alkaline phosphatase ≤ 2.5 x ULN

- Renal

- Creatinine ≤ 1.5 x ULN

- Serology (within 6 months of study entry)

- HIV negative

- Hepatitis C negative

- LDH up to 2 x ULN

- Participants must be 18 years or older at study entry.

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

Exclusion Criteria:

- Patients who have had brain metastases unless they meet the criteria outlined in the
inclusion criteria section of the protocol.

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

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

- Interferon Therapy

- Interleukin-2 or other interleukins.

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

- Participants may not have been vaccinated previously with any of the synthetic
phosphopeptides included in this protocol.

- 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. The methods are specified in the consent form and
include the following: Norplant, IUD, Dep-Provera, Birth Control Pills, Birth Control
Patch, and Sterilization. The following may be used if combined with other birth
control methods: Condoms, Jellies or foam, Diaphragm, Rhythm, Withdrawal, Sponge, or
Cervical cap.

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

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

- Participants must not have known inflammatory conditions of the gastrointestinal
tract (oropharynx, esophagus, stomach, small bowel, colon, rectum, or anus) or the
respiratory tract (airway and lungs) of autoimmune, infectious, or other cause.
Examples may include but are not limited to, gastritis, C. difficile colitis,
radiation proctitis, bronchitis. Patients may have had such conditions in the past if
they have recovered completely at least 3 months prior, and are not expected to have
relapses of the condition.

- 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