Inclusion Criteria:

* Patients must have a diagnosis of metastatic melanoma which is measurable 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 of 0 or 1 ECOG PS scale (see Appendix B).
* 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 per Loyola University Medical Center pathologic review from FNA/core/excisional biopsy of lesion.
* Cardiac ejection fraction >50% as determined by screening echocardiogram.
* Patients that have undergone treatment with anti-CTLA-4 (Cytotoxic T-Lymphocyte Antigen 4) antibody must have at least 3 months from last dose of CTLA-4 antibody before they can be enrolled into this study.
* The patients BRAF mutation status at position 600 must be known prior to enrollment. Patients with V600E mutations are eligible if they have failed Vemurafenib therapy or have been offered Vemurafenib therapy and refused.
* Patients treated with prior Interleukin-2 will be allowed to be in this study.

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 six 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/men of reproductive potential must have agreed to use an effective contraceptive method.
* Patients whose BRAF V600E mutation status is unknown, have the BRAF V600E mutation and are responding to Vemurafenib therapy, or have the BRAF V600E mutation and have not been offered the option of receiving Vemurafenib therapy for the treatment of their melanoma.
* No other 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 five years.
* Patients that have undergone Tyrosinase immunotherapy.
* 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 109/L
* Platelet count less than 100 x 109/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 (e.g., 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.