We conducted a phase 1/2 study of the combination of 5-aza-2′-deoxycytidine (decitabine) and the histone deacetylase inhibitor valproic acid (VPA) in patients with advanced leukemia, including older untreated patients. A group of 54 patients were treated with a fixed dose of decitabine (15 mg/m² by IV daily for 10 days) administered concomitantly with escalating doses of VPA orally for 10 days. A 50 mg/kg daily dose of VPA was found to be safe. Twelve (22%) patients had objective response, including 10 (19%) complete remissions (CRs), and 2 (3%) CRs with incomplete platelet recovery (CRp). Among 10 elderly patients with acute myelogenous leukemia or myelodysplastic syndrome, 5 (50%) had a response (4CRs, 1CRp's). Induction mortality was observed in 1 (2%) patient. Major cytogenetic response was documented in 6 of 8 responders. Remission duration was 7.2 months (range, 1.3-12.6+ months). Overall survival was 15.3 months (range, 4.6-20.2+ months) in responders. Transient DNA hypomethylation and global histone H3 and H4 acetylation were induced, and were associated with p15 reactivation. Patients with lower pretreatment levels of p15 methylation had a significantly higher response rate. In summary, this combination of epigenetic therapy in leukemia was safe and active, and was associated with transient reversal of aberrant epigenetic marks. This trial was registered at www.clinicaltrials.gov as #NCT00075010.