Vaccines contain substances that help us make antibodies. Different antibodies help protect us against a variety of harmful things. GD2 and GD3 gangliosides are substances found on the surface of most melanoma cells. They are also occasionally found on some normal cells. Large quantities of antibodies called monoclonal antibodies have been prepared in the laboratory against GD2 and GD3 and given to patients with metastatic melanoma. In about 10% of cases this has resulted in clinically relevant regression of melanomas. These monoclonal antibodies are not currently available or used in the clinic but studies in the laboratory indicate that vaccines against GD2 and GD3 can be as effective as monoclonal antibodies.

In this trial we wish to raise the level of antibodies in your blood against GD2 and GD3. We will vaccinate you with the modified forms of GD2 called GD2 lactone and GD3 called GD3 lactone (GD3L), all attached to the antibody booster KLH, and mixed with the immune booster (immunologic adjuvant) QS-DG. While over a thousand patients have received vaccines with QS-21, the QS-DG used here is synthesized for the first time at MSKCC and is referred to as QS-DG rather than QS-21 which is purified from tree bark. QS-21 and QS-DG are, to the best of our knowledge chemically identical. It is unknown if using this bivalent vaccine will raise the level of antibodies in your blood to either ganglioside. It is unknown if raising the level of antibodies in your blood will lower your risk of relapse. This study will check your blood for production of antibodies, and check you for side effects.

Inclusion Criteria:

• Patients ≥18 with AJCC stage III or IV melanoma two weeks to one year after becoming clinically free of disease will be eligible.
• For all patients' pathology slides must be reviewed by the Memorial Hospital Department of Pathology to confirm diagnosis of cutaneous melanoma.
• All patients must have a Karnofsky performance status of ≥80.
• Patients may have received previous radiation, chemotherapy or systemic immunotherapy (completed at least 4 weeks prior to vaccination).
• A CBC must be performed within 2 weeks prior to vaccination with the WBC > or equal to 3.0 cells/mm3, Platelets >100,000/mm3,
• A screening profile must be performed within 2 weeks prior to vaccination with the total bilirubin ≤ 2.0, and other LFTs within normal limits for patient's age.
• Chest, abdomen and pelvic CT or MRI must be performed within 4 weeks of the initiation of treatment showing no evidence of disease.
• Women of child bearing potential and sexually active males must be counseled to use an accepted and effective method of contraception (including abstinence) while on treatment.

Exclusion Criteria:

• Patients previously treated with KLH or ganglioside containing vaccines, or monoclonal antibodies against gangliosides are not eligible.
• Women must not be pregnant (negative βHCG within 2 weeks of vaccination if of childbearing potential).
• Patients with other active cancers within the past 2 years, (excluding basal cell, squamous carcinomas of the skin or cervical carcinoma-in-situ) are not eligible.
• Any medical condition which might make it difficult for the patient to complete the full course of treatments or to respond immunologically to them is grounds for exclusion, at the discretion of the Principal Investigator.
• Patients requiring anti-inflammatory medications such a steroids, NSAIDS or full dose aspirin are not eligible.
• There must be no evidence of metastatic disease at the time of the first vaccine. However, patients who develop new metastases during treatment may continue on treatment as long as no systemic treatment is indicated and any local treatment such as surgical resection or radiation would not cause a delay in vaccination or two weeks or more.