Valproic acid is a medication that is currently used in the prevention of seizures, bipolar disorder, and migraine headaches. Researchers hope that it may improve the effects of decitabine. Decitabine is a chemotherapy drug with known activity in leukemia and myelodysplastic syndromes.

Recent studies have shown synergy between demethylating agents and histone deacetylase inhibitors. It has been shown that both DNA methylation and histone deacetylation work together in affecting gene expression.

Therefore, drugs that inhibit DNA methylation and those that inhibit histone deacetylase can reactivate silenced genes in combination better than they can individually. Decitabine (5 aza-2'deoxycytidine), a drug that produces marked DNA hypomethylator, has demonstrated antileukemic activity at low doses. There are several drugs that have been shown to have histone acetylase activity. One of these is valproic acid that has been used safely for many years as an anti-seizure medication.

Inclusion Criteria:

1. FOR PHASE I COMPONENT OF THE STUDY: Patients with refractory or relapsed: acute myelogenous leukemia (AML), acute lymphocytic leukemia (ALL), and myelodysplastic syndrome (MDS) are eligible. Patients with chronic lymphocytic leukemia (CLL) are eligible if fludarabine based therapy has failed. Patients with chronic myeloid leukemia (CML) are eligible if they have documented hematologic resistance to imatinib mesylate or have not achieved or lost any cytogenetic response to imatinib mesylate after 12 months of therapy.
2. Untreated patients older than 60 years of age with AML or MDS who refuse or are not eligible for frontline chemotherapy, are eligible.
3. Performance status of =/< 2 by the ECOG scale.
4. Signed informed consent indicating that patients are aware of the investigational nature of this study in keeping with the policies of UTMDACC.
5. Age > 2 years.
6. Patients must have been off chemotherapy for 2 weeks prior to entering this study and recovered from the toxic effects of that therapy, unless there is evidence of rapidly progressive disease. Use of hydroxyurea for patients with rapidly proliferative disease is allowed for the first two weeks on therapy. Imatinib mesylate (Gleevec) and anagrelide must also be stopped 2 weeks prior to entering this study.
7. Adequate liver function (bilirubin of < 2mg%, SGPT < 3 x ULN) and renal function (creatinine < 2mg%).
8. Women of childbearing potential must practice contraception. Men and women must continue birth control for the duration of the trial.
9. INCLUSION OF PHASE II PORTION OF THE STUDY: As in the phase I portion but only patients with AML or high-risk MDS (blasts > or = 10%), including untreated patients older than 60 years of age with AML or MDS who refuse or are not eligible for frontline chemotherapy, will be eligible in this portion of the study.

Exclusion Criteria:

1. Nursing and pregnant females are excluded.
2. Patients with active and uncontrolled infections are excluded.
3. Patients with a known ornithine transcarbamylase disorder, history of unexplained coma or a family history of ornithine transcarbamylase disorder are excluded from this study.
4. Uncontrolled intercurrent illness including, but not limited to symptomatic congestive heart failure, unstable angina pectoris, pancreatitis, psychiatric illness that would limit compliance with study requirements.
5. Patients with history of hepatitis B, C, alcoholic liver disease or evidence of hepatopathy will be excluded.
6. Patients already receiving valproic acid or receiving other anticonvulsivants will be excluded.
7. Untreated patients younger than 60 years will not be candidates for this study.