Inclusion Criteria:

* Patients must have a diagnosis of metastatic melanoma which is evaluable either clinically or radiologically.
* Patients must be 18 years of age or older.
* Patients must consent to be in the study and must have signed and dated an approved consent form, which conforms to federal and institutional guidelines.
* Patients must have a performance status (PS) of 0 or 1 ECOG PS scale.
* Patients must have the ability to provide written informed consent prior to study specific screening procedures, with the understanding that the patient has the right to withdraw from the study at any time.
* Patients melanoma must be positive for both tyrosinase and HLA-A2 pathologic review from FNA, core or excisional biopsy of lesion.
* Cardiac ejection fraction greater than 50 percent as determined by screening echocardiogram.
* Patients that have undergone treatment with anti-CTLA-4, Cytotoxic T-Lymphocyte Antigen 4, antibody must have at least 6 weeks from last dose of CTLA-4 antibody and evidence of tumor progression before they can be enrolled into this study.
* Patients that have undergone treatment with anti-PD-1, Programmed Death Receptor 1, Blockade or anti-PD-L1 antibody must have at least 4 weeks from last dose of antibody and evidence of tumor progression before they can be treated in this study.
* Patients with V600E mutations are eligible if they have failed an approved BRAF inhibitor or MEK inhibitor therapy or have refused treatment with an approved BRAF inhibitor or MEK inhibitor.
* Patients treated with prior Interleukin-2 (IL-2) are eligible.
* Sufficient cardiopulmonary reserve for IL-2 per institutional guidelines.

Exclusion Criteria:

* Special classes of subjects such as fetuses, pregnant women, children, prisoners, institutionalized individuals, or others who are likely to be vulnerable.
* ECOG performance status of 2 or greater.
* Patients with a history metastatic melanoma involving the brain will be excluded if they have active disease or have had active disease within the prior three months that was not controlled with surgery or radiotherapy.
* Patients taking steroids for disease control or pain management
* Patients must not be pregnant or nursing because of the potentially harmful effects of these agents on a developing fetus. Women or men of reproductive potential must have agreed to use an effective contraceptive method.
* Patients whose BRAF V600 mutation status is unknown should undergo an attempt to determine this information, patients who have a BRAF V600 mutation and are responding to BRAF with or without MEK inhibitor therapy, or have a BRAF V600 mutation and have not been offered the option of receiving BRAF with or without MEK inhibitor therapy for the treatment of their melanoma are excluded.
* No prior malignancy is allowed except for the following- adequately treated basal cell or squamous cell skin cancer, in situ cervical cancer, adequately treated Stage I or II cancer from which the patient is currently in complete remission, or any other cancer from which the patient has been disease-free for two years.
* Patients that have undergone immunotherapy targeting tyrosinase.
* Patients that have undergone immunotherapy in combination with non-myeloablative chemotherapy.
* Any of the following abnormal laboratory values Absolute neutrophil count less than 1.5 x 10\^9/L Platelet count less than 100 x 10\^9/L Serum bilirubin greater than 1.5 x upper limit of normal ULN Serum ALT, AST greater than 2.5 x ULN Serum ALP greater than 2 x ULN Serum Albumin less than 2.5 g dL International Normalized Ratio, INR greater than 1.5 Serum creatinine calculated creatinine clearance by the method of Cockcroft and Gault, less than 50mL min.
* Patients should not have any evidence of active or uncontrolled infection requiring treatment with antibiotics.
* Any severe or poorly controlled systemic disease, for example hypertension, clinically significant cardiovascular, pulmonary, or metabolic disease, disorders of wound-healing, ulcer or bone fracture.
* Patients who have received any chemotherapy or investigational treatment within 4 weeks of study start.
* Known infection with HIV, HBV, or HCV.
* Known hypersensitivity to any of the components of the study drugs.
* Patients assessed by the investigator to be unable or unwilling to comply with the requirements of the protocol.