Parallel Phase I/II Trial of Decitabine and Peg-Interferon in Melanoma: Phase I Portion

Inclusion Criteria:

1. Patients must have pathologically confirmed malignant melanoma that is unresectable stage III or stage IV.
2. Patients must have measurable disease as defined by RECIST criteria.
3. No more than two prior chemotherapy for unresectable stage III or IV melanoma.
4. Patients must be \>/= 28 days beyond the last administration of anticancer therapy, and must have recovered from the toxicities of prior therapy. If the patient was recently treated with a nitrosurea, they must be \>/= 42 days beyond the last administration.
5. Patients must have no other active malignancies. Patients with prior history of any in situ cancer, lobular carcinoma of the breast in situ, cervical cancer in situ, atypical melanocytic hyperplasia or Clark I melanoma in situ or basal or squamous cell skin cancer are eligible. Patients with other malignancies are eligible, if their disease has been inactive for 2 years prior to the time of study entry.
6. Patients must be \>/= 18 years of age.
7. Patients must give written informed consent prior to initiation of therapy in keeping with the policies of the institution. Patients with a history of major psychiatric illness must be judged able to fully understand the investigational nature of this study and the risks associated with the therapy.
8. Women of childbearing potential (WOCBP) must not be pregnant (negative urine human chorionic gonadotropin (HCG) within 2 weeks of treatment) or lactating. A WOCBP is defined as a woman who has not undergone a hysterectomy or who has had menses at any time in the preceding 24 consecutive months.
9. Women of childbearing potential and sexually active males must be counseled to use an accepted and effective method of contraception (including abstinence) while on treatment and for a period of 3 months after completing or discontinuing treatment.
10. Patients must have Eastern Cooperative Oncology Group (ECOG) performance status 0 or 1.
11. Patients must have adequate organ and marrow function, measured within 14 days of study entry, as defined below: All Patients: - Absolute neutrophil count \>/=1,500/uL - Platelets \>/=100,000/uL - Creatinine (serum) \</= 2.0 mg/dL - Total bilirubin \</= 1.5 mg/dL - AST(SGOT)/ALT(SGPT) \</= 2.5 X Institutional Upper Limit of Normal (IULN)
12. Patients with any number of prior targeted or cytokine therapies, but no more than two chemotherapy containing regimens.

Exclusion Criteria:

1. Patients with active autoimmune disorders or who are receiving immunosuppressive therapy (including steroids or methotrexate) for any indication are excluded. An exception may be made, by the PI, to include patients with adrenal insufficiency requiring physiologic steroid hormone replacement only.
2. Patients who have previously received adjuvant high dose interferon.
3. Patients may not receive any other investigational agents within four weeks of study entry. Patients may not receive any other investigational agents while on study.
4. Patients who have had major surgery within 2 weeks prior to entering the study, or have otherwise not adequately recovered from prior surgery.
5. Patients who have had palliative radiation therapy within 2 weeks prior to entering the study.
6. Patients with brain metastases.
7. Patients with a history of active ischemic heart disease or cerebro-vascular disease, congestive heart failure (NYHA class \>2) or anginal syndrome requiring ongoing medical treatment.
8. Patients with myocardial ischemia (MI), stroke, or transient ischemic attack (TIA) within the last 6 months.
9. Patients with a diagnosis or evidence of organic brain syndrome or significant impairment of basal cognitive function or any psychiatric disorder that might preclude participation in the protocol.
10. Patients with a history of central nervous system (CNS) demyelinating, inflammatory disease or hereditary or acquired peripheral neuropathy.
11. Patients with known history of HIV and hepatitis infection or any other significant medical or surgical condition or psychiatric disorder that may interfere with the completion of this trial or with the evaluation of safety and efficacy of the study combination.
12. Patients with thyroid dysfunction not responsive to therapy.