We investigated the antiproliferative effect of genistein, and its antileukemia effect in combination with cytosine arabinoside (ara-C) in acute myeloid leukemia (AML). Optimal dosage of genistein as single agent and in combination with ara-C was first determined in vitro. Genistein demonstrated a dose- and time-dependent inhibition of cell proliferation, induction of apoptosis, and cell-cycle arrest at G(2)/M phase. Gene-expression profiles revealed mitogen-activated protein kinase (MAPK) signaling as one of the most affected biological pathways. Phosphatidylinositol 3 kinase, protein kinase A, protein kinase C, MAPK kinase 4, KIT, PIM1, and transforming growth factor-beta receptor 1, were significantly downregulated by genistein. To test whether genistein could augment the antiproliferation activity of ara-C, two groups of severe combined immunodeficient mice were inoculated with NB4 and HL-60 cells, respectively, followed by treatment with either genistein or combination of genistein and ara-C. The combination treatment significantly inhibited tumor growth, and improved survival of NB4 (p = 0.0031) and HL-60 (p = 0.0007) xenograft mice. Our present study highlighted the schedule-dependent synergistic antileukemia effect of genistein with chemotherapy in both in vitro and in vivo models. This novel combination could potentially be a promising regimen for treatment of AML.