The goal of this clinical research study is to learn if high-dose interleukin-2 (HDIL-2), when given in combination with recMAGE-A3 + AS15 ASCI (Antigen-Specific Cancer Immunotherapeutic), can help to control unresectable or metastatic melanoma in patients whose tumor tissue has the MAGE-A3 protein. The safety of this drug combination will also be studied. Researchers will also use samples of the original tumor or metastatic tissue (for example, lymph nodes or liver or lung) that are collected during screening to study if response to the study drug is related to the genes in the tissue.

The Study Drugs:

HDIL-2 is similar to a hormone naturally found in the body that boosts the immune system by helping "natural killer" (NK) cells live longer and work better. NK cells are a type of white blood cell that kill other cells, and they may kill cancer cells.

ASCI is a immunotherapy designed to teach your immune system to fight cancer in the same way that you are given vaccines to prevent disease by teaching your immune system to fight an infection caused by germs. Because the cancer is made by your own body, the immune system does not recognize the cancer cells as being harmful. Your immune system needs to be "trained" to recognize the cancer cells. This is done by injecting a protein (the MAGE-A3 protein) that is found in the tumor and training your body to recognize it and to destroy the cells that have this protein. This may increase the effectiveness of IL-2 by slowing the growth of the cancer cells, which may cause them to die.

Study Drug Administration:

If you are found to be eligible to take part in this study, you will begin the study drugs within 14 days of signing the second consent form. To receive the study drugs, you will be admitted to the hospital, either in the intensive care unit (ICU) or a specifically designated nursing unit where study drugs can be administered, on Day 2 of each cycle and may remain in the hospital for up to 7 days each cycle.

You may receive a total of 24 ASCI doses either in combination with HDIL-2 or alone. You may receive the study drugs in combination for up to 30 weeks. After that, you may receive the ASCI study medication alone for up to 157 more weeks.

Cycle 1 is 14 days (Weeks 1 and 2):

• On Day 1 of Cycle 1, you will receive the ASCI study medication as an injection. Each injection will be given in the muscle of your upper arm or in your thigh. You will be watched in the clinic for at least 30 minutes after each injection.
• On Day 2 (+/- 2 business days), you will receive HDIL-2 through a catheter (a small plastic tube that is put into your vein under your collar bone or in your arm) over 15 minutes. HDIL-2 treatment will be delayed in cycles 2, 3, 4, 5, 6, 7, or 8 until all HDIL-2 related side effects either go away or the study doctor thinks they are under control.

Cycle 2 is 42 days (Weeks 3-8):

• On Day 1 of Weeks 3, 5, and 7 (+/- 2 business days) , you will receive the ASCI study medication as an injection.
• On Day 2 of Week 3 (+/- 2 business days), you will receive HDIL-2 by vein.

Cycle 3 is 14 days (Weeks 9 and 10):

• On Day 1 of Week 9 (+/- 2 business days), you will receive the ASCI study medication as an injection.
• On Day 2 of Week 9 (+/- 2 business days), you will receive HDIL-2 by vein.

Cycle 4 is 49 days (Weeks 11-17):

• On Day 1 of Weeks 11 and 15 (+/- 2 business days), you will receive the ASCI study medication as an injection.
• On Day 2 of Week 11 (+/- 2 business days), you will receive HDIL-2 by vein.

Cycle 5 is 21 days (Weeks 18-20):

• On Day 1 of Week 18 (+/- 2 business days), you will receive the ASCI study medication an injection.
• On Day 2 of Week 18 (+/- 2 business days), you will receive HDIL-2 by vein.

Cycle 6 is 42 days (Weeks 21-26):

• On Day 1 of Weeks 18, 21, and 24 (+/- 2 business days), you will receive the ASCI study medication as an injection.
• On Day 2 of Weeks 18 and 21 (+/- 2 business days), you will receive HDIL-2 by vein.

Cycle 7 is 21 days (Weeks 27-29):

• On Day 1 of Week 27 (+/- 2 business days), you will receive the ASCI study medication as an injection.
• On Day 2 of Week 27(+/- 2 business days), you will receive HDIL-2 by vein.

Cycle 8 is 28 days (Weeks 30-33):

• On Day 1 of Week 30 (+/- 2 business days), you will receive the ASCI study medication as an injection.
• On Day 2 of Week 30 (+/- 2 business days), you will receive HDIL-2 by vein.

On Day 1 of Weeks 34, 40, 46, 52, 64, 76, 88, and 100 (+/- 2 business days), you will receive the ASCI study medication as an injection.

Study Visits:

On Day 1 of Weeks 1, 3, 5, 7, 9, 11, 15, 18, 21, 24, 27, and 30 (+/- 2 business days):

• You will have a physical exam, including measurement of your weight and vital signs. °Blood (about 2 tablespoons) will be drawn for routine tests.
• You will be asked about any side effects you may be having and drugs you are taking.

On Day 2 of Weeks 1, 3, 5, 7, 9, 11, 18, 21, 27, and 30 (+/- 2 business days):

• Blood (about 2 tablespoons) will be drawn for routine tests.
• You will be asked about any side effects you may be having and drugs you are taking.

During Weeks 8, 17, 26, 33, 39, 51, 63, 75, 87, 99, 123, 147, 171, and 195 (+/- 1 week):

• You will have and a CT scan of your chest, abdomen, and pelvis to check the status of the disease.
• You will also have an MRI scan or CT scan of the brain to check the status of the disease.
• You will have photographs of your lesions taken if indicated by your doctor.

On Day 1 of Weeks 34, 40, 46, 52, 64, 76, 88, 100, 124, 148, 172, and 196 (+/- 2 business days):

• You will have a physical exam, including measurement of your weight and vital signs.
• Blood (about 2 tablespoons) will be drawn for routine tests.
• You will be asked about any side effects you may be having and drugs you are taking.

Additional Blood Draws:

Additional blood (about 4 tablespoons each time) will be drawn for laboratory tests to look at how the study drug combination may affect the immune system. These blood draws will be collected on Day 1 of cycle 1 and again during cycle 1 48 hours after the last dose of IL-2. Additional blood draws (about 4 tablespoons each time) will also Part of the blood drawn for these tests will be sent to GSK Biologicals (or a contracted laboratory) for testing.

Length of Study:

You may continue to receive the study drug combination for up to 8 cycles (33 weeks) and ASCI alone for up to 76 more weeks (+/- 2 business days). If you continue beyond completing 8 cycles of HDIL-2, you will receive the ASCI on Day 1 (+/- 2 business days) every 6 weeks for 4 doses (weeks 34, 50, 46, and 52), then on Day 1 (+/- 2 business days) every 12 weeks (weeks 64, 76, 98, and 110) for 4 doses, then on Day 1 (+/- 2 business days) of every 24 weeks (Weeks 134, 158, 182, and 187) for 4 doses.

You will be taken off the study therapy early if the disease gets worse, you experience intolerable side effects, or the study doctor thinks it is in your best interest. If you are removed from the study because of intolerable side effects, you will be followed weekly by either a phone call or clinic visit until the side effect is tolerable.

End-of-Dosing Visit:

After receiving the last dose of study drug combination, you will have an end-of-dosing visit:

• Your medical history will be reviewed and you will be asked about any side effects you may be having and drugs you are taking.
• You will have a physical exam, including measurement of your weight and vital signs.
• Blood (about 3 tablespoons) will be drawn for routine tests and ANA testing.

Follow-Up Visits:

You will have follow-up visits after your last dose of study drug, if the disease does not get any worse. Starting after the last dose of study drug, you will have 1 visit every 3 months for the 1st year, every 4 months for the 2nd year, every 6 months for the 3rd and 4th year, then once a year for up to 10 years (+/- 2 business days). At these visits, the following will be performed:

• You will have a physical exam, including measurement of your weight and vital signs.
• If the study doctor thinks it is needed, blood (about 2 tablespoons) will be drawn for routine tests.
• If the study doctor thinks it is needed, you will have a chest x-ray, CT scan of your chest, abdomen, and pelvis, and/or MRI scan or CT scan of the brain to check the status of the disease.

If the disease begins to get worse, information about the status of your health will be collected every 2 months. If you are not able to come into the clinic to complete this visit, you will be asked for this information over the phone. The phone call should last about 10-15 minutes each time.

This is an investigational study. IL-2 is commercially available and FDA approved for the treatment of metastatic melanoma. HDIL-2 is a higher dose than the standard approved dose of IL-2. The ASCI study medication is not FDA approved or commercially available. It is currently being used for research purposes only.

Up to 30 patients will take part in this study. All will be enrolled at MD Anderson.

Inclusion Criteria:

1. STEP 1 Written informed consent has been obtained from the patient before the performance of any protocol-specific procedure.
2. Male or female patient with histologically proven, measurable unresectable or metastatic cutaneous melanoma
3. Patient is >/= 18 years of age.
4. Formalin-fixed paraffin-embedded (FFPE) tumor tissue must be available for MAGE-A3 expression screening test from cutaneous, subcutaneous, lymph node lesion, lung or liver lesion. Archival FFPE tumor tissue can be provided for the MAGE-A3 screening test, as long as the FFPE tumor tissue was obtained from a biopsy or resection and no systemic chemotherapy, immunotherapy or targeted therapy has been received by the patient between the tumor collection and the MAGE-A3 screening test. Fresh tumor tissue in RNAlater must be also available for gene signature testing. Patients must have at least one biopsiable cutaneous, subcutaneous, lymph node lesion, The tumor sample should be preferably from the same lesion as the FFPE tumor tissue. Cutaneous lesions must measure >/= 4mm and lymph nodes, subcutaneous, lung or liver lesions must measure >/= 1cm.
5. STEP 2 ANA (antinuclear antibody) titer < 1:80
6. STEP 2 The patient's tumor shows expression of MAGE-A3 gene.
7. ECOG performance status of 0 or 1.
8. WBC >/= 3000/mm^3 and Hemoglobin >/= 9 g/dl
9. Platelet count >/= 100,000/mm^3.
10. Normal AST and ALT except for patients with liver metastases, in which serum ALT and AST </= 2.5 X upper limit of normal (ULN) will be permitted.
11. Creatinine </= 1.5 mg/dL
12. Normal total bilirubin except for patients with liver metastases, in which total bilirubin </= 1.5 X ULN will be permitted (patients with Gilbert's syndrome must have a total bilirubin less that 3.0 mg/dL).
13. LDH </= 2 X ULN
14. Stress cardiac test (stress thallium, stress MUGA, dobutamine echocardiogram or other stress test that will rule out cardiac ischemia) with estimated ejection fraction >50% within 6 months of signing consent form
15. Pulmonary function tests showing FEV1 > 65% or FVC > 65% of predicted within 6 months of signing consent form
16. Women of childbearing potential (WOCBP) must be using an adequate method of contraception prior to treatment, throughout the study, and for up to 8 weeks after the last dose of investigational product, in such a manner that the risk of pregnancy is minimized. In general, the decision for appropriate methods to prevent pregnancy should be determined by discussions between the investigator and the study subject. WOCBP include any female who has experienced menarche and who has not undergone successful surgical sterilization (hysterectomy, bilateral tubal ligation, or bilateral oophorectomy) or is not post-menopausal. Post-menopause is defined as: Amenorrhea for 12 consecutive months without another cause, or For women with irregular menstrual periods and taking hormone replacement therapy (HRT), a documented serum follicle stimulating hormone (FSH) level 35 mIU/mL.
17. (Continued #16) Women who are using oral contraceptives, other hormonal contraceptives (vaginal products, skin patches, or implanted or injectable products), or mechanical products such as an intrauterine device or barrier methods (diaphragm, condoms, spermicides) to prevent pregnancy, or are practicing abstinence or where their partner is sterile (eg, vasectomy) should be considered to be of childbearing potential. WOCBP must have a negative serum or urine pregnancy test (minimum sensitivity 25 IU/L or equivalent units of HCG) within 14 days before the start of treatment.
18. Men must also agree to use an adequate method of contraception.

Exclusion Criteria:

1. The patient has at any time received systemic chemotherapy, immunotherapy or targeted therapy (except for isolated limb perfusion, interferon, or radiation in the adjuvant setting, as long as this was performed at least 4 weeks before first study treatment administration).
2. Brain metastasis or history of brain metastasis.
3. Any types of melanoma other than cutaneous, i.e. ocular or mucosal .
4. The patient received any cancer immunotherapeutic containing a MAGE-A3 antigen.
5. Patients with a history of second malignancies are eligible provided that they have been free of recurrence from secondary malignancy for at least 3 years, does not include squamous cell carcinoma, basal cell carcinoma, or carcinoma in situ.
6. The patient has a history of an autoimmune disease such as, but not limited to, multiple sclerosis, lupus, rheumatoid arthritis, and inflammatory bowel disease or an antinuclear antibody (ANA) titer > 1:80.
7. The patient has a history of allergic disease or reactions likely to be exacerbated by any component of the study investigational compound.
8. The patient has a family history of congenital or hereditary immunodeficiency.
9. Known to be positive for viral hepatitis B or C (HBsAg or Anti HCV) or HIV (HIV antibodies) Patients should have a negative test within 6 months of starting treatment.
10. Systemic steroid therapy, steroid-containing compounds or any other immunosuppressive agents or to be used for more than 7 consecutive days (at a dose of prednisone or equivalent of >/= 0.125 mg/kg/day).
11. The patient has psychiatric or addictive disorders that may compromise his/her ability to give informed consent, or to comply with the trial procedures. Each patient will be evaluated by the principal investigator or his designee.
12. The patient has concurrent severe medical problems, unrelated to the malignancy, that would significantly limit full compliance with the study or expose the patient to unacceptable risk. Each patient will be evaluated by the principal investigator or his designee.
13. Initiation of another anti-cancer therapy.
14. For female patients: the patient is pregnant or lactating.
15. WOCBP who are unwilling or unable to use an acceptable contraceptive method to avoid pregnancy.

Throughout treatment up to 3 years & 9 months.