The goal of this clinical research study is to learn if the combination of vosaroxin and decitabine can help to control AML or MDS. The safety of these drugs will also be studied.

Study Groups:

If you are found to be eligible to take part in this study, you will be assigned to a study group based on when you join this study. Up to 4 groups of up to 6 participants will be enrolled in the Phase I portion of the study, and up to 60 participants will be enrolled in Phase II.

If you are enrolled in the Phase I portion, the dose of vosaroxin you receive will depend on when you joined this study. The first group of participants will receive the highest dose level of vosaroxin. If no intolerable side effects are seen, the study will move on to Phase II. If intolerable side effects are seen, each new group will receive a lower dose of vosaroxin than the group before it until the most tolerable dose is found.

If you are enrolled in the Phase II portion, you will receive vosaroxin at the highest dose that was tolerated in the Phase I portion.

All participants will receive the same dose level of decitabine.

Study Drug Administration:

You will receive the study drugs in cycles. The study cycles will be 4-12 weeks long, depending on if/how the disease responds to the treatment, how your bone marrow reacts to treatment, and what the doctor thinks is in your best interest.

On Days 1-5 of each study cycle, you will receive decitabine by vein over about 1 hour. On Days 1 and 4 of each cycle, you will also receive vosaroxin by vein over 8-10 minutes, before you receive decitabine. Depending on how the disease responds to the study drugs, the number of days you receive the study drug may change. Your doctor will discuss this with you.

The first 2 cycles are called Induction Cycles. All cycles after that are called Consolidation Cycles. All participants will receive Induction Cycle 1. If the study doctor thinks it is needed, you will also receive Induction Cycle 2. If after that the study doctor thinks it is in your best interest, you will receive up to 5 Consolidation Cycles of treatment.

Study Visits:

On Day 1 of each cycle, you will have a physical exam.

Every week, blood (about 1 tablespoon) will be drawn for routine tests. If at any point you appear to have a response to the study drugs, this blood will then be drawn every 1-2 weeks while you are still receiving the study drugs. If your doctor thinks it is needed, more blood may need to be drawn.

On Day 21 of Cycle 1 (+/- 7 days), then every 4 weeks after that, you will have a bone marrow aspiration and/or biopsy to check the status of the disease. If the doctor thinks it is needed, these may be done more or less often, depending on your response to the study drugs.

Length of Study:

You may receive the study drugs for up to 7 cycles. You will be taken off study if the disease gets worse, intolerable side effects occur, or if the study doctor thinks it is in your best interest.

Your participation in the study will be over after the follow-up period.

End-of-Study Visit:

If you are taken off study or if you leave the study early, you will have an end-of-study visit. At this visit:

Blood (about 2-3 teaspoons) will be drawn for routine tests. If the study doctor thinks it is needed, you will have a bone marrow aspiration.

You will then be contacted during a study visit or called and asked about any side effects you may be having 30 days after the end-of-study visit. This call will last about 5 minutes.

Follow-up:

If you do not leave the study early, you will have follow-up visits and calls for up to 5 years after you stop receiving the study drugs.

Every 4-8 weeks, blood (about 1 tablespoon) will be drawn for routine tests. If you cannot return to the clinic, you may have blood drawn at a clinic close to your home.

Every 3-6 months, you will be contacted during a clinic visit and asked how you are doing. If you cannot make it to the clinic for this visit, you will be called. The phone call should last about 5 minutes.

This is an investigational study. Vosaroxin is not FDA approved or commercially available. It is currently being used for research purposes only. Decitabine has been approved by the FDA for the treatment of MDS, which is a precursor of AML, but has not been approved for the treatment of AML. The use of these drugs in combination is investigational. The study doctor can explain how the drugs are designed to work.

Up to 84 patients will take part in this study. All will be enrolled at MD Anderson.

Inclusion Criteria:

1. Previously untreated AML (>/= 20% blasts). Patients with high-risk MDS (defined as having >/= 10% blasts in the bone marrow) or patients with Chronic Myelomonocytic Leukemia (CMML) (having >/= 10% blasts in the bone marrow) may also be eligible after discussion with Principal Investigator (PI). Prior therapy with hydroxyurea, biological or targeted therapy (e.g. FLT3 inhibitors, other kinase inhibitors), or hematopoietic growth factors is allowed, however prior therapy with chemotherapy agents for the disease under study is not allowed. Patients may have received one dose of cytarabine (up to 2 g/m2) administered at presentation for control of hyperleucocytosis. For patients with prior MDS or CMML who transformed to AML, therapy received for MDS is not considered as prior therapy for AML.
2. Age >/= 60 years and not candidates for conventional cytotoxic chemotherapy or refuse it; OR patients below the age of 60 years who are considered unfit and/or unable to tolerate standard chemotherapy at the discretion of the treating physician or the principal investigator. "
3. Eastern Cooperative Oncology Group performance status </= 2.
4. Adequate hepatic (serum total bilirubin </= 1.5 x upper limit normal (ULN), alanine aminotransferase and/or aspartate transaminase </= 2.5 x ULN) and renal function (creatinine </= 2.0 mg/dL).
5. Left ventricular ejection fraction (LVEF) at least 40% by multiple gated acquisition (MUGA) scan or echocardiogram (ECHO)
6. Patients must be willing and able to review, understand, and provide written consent before starting therapy.
7. Females must be surgically or biologically sterile or postmenopausal (amenorrheic for at least 12 months) or if of childbearing potential, must have a negative serum pregnancy test within 14 days before the start of the treatment. Women of childbearing potential may have a urine pregnancy test, instead of a serum pregnancy test. If either the serum or urine pregnancy test is equivocally negative the patient will be eligible for the protocol. Women of childbearing potential must agree to use an adequate method of contraception during the study until 30 days after the last treatment. Males must be surgically or biologically sterile or agree to use an adequate method of contraception during the study until 30 days after the last treatment.

Exclusion Criteria:

1. New York Heart Association class III or IV heart disease, active ischemia or any other uncontrolled cardiac condition such as active angina pectoris, clinically significant cardiac arrhythmia that requires therapy in the opinion of the treating physician or PI, uncontrolled hypertension (blood pressure > 160 systolic and > 110 diastolic not responsive to antihypertensive medication), uncontrolled diabetes mellitus in the opinion of the treating physician or PI, or uncontrolled congestive heart failure in the opinion of the treating physician or PI.
2. Myocardial infarction in the previous 12 weeks (from the start of treatment).
3. Active and uncontrolled disease/infection as judged by the treating physician
4. Pregnant or breastfeeding
5. Known Human Immunodeficiency Virus seropositivity
6. Any other medical, psychological, or social condition that may interfere with study participation or compliance, or compromise patient safety in the opinion of the investigator or medical monitor
7. Acute promyelocytic leukemia (APL).

Up to 2 years 11 months