Accurate assessment of changes in cellular differentiation status in response to drug treatments or genetic perturbations is crucial for understanding tumorigenesis and developing novel therapeutics for human cancer. We have developed a novel computational approach, the Lineage Maturation Index (LMI), to define the changes in differentiation state of hematopoietic malignancies based on their gene expression profiles. We have confirmed that the LMI approach can detect known changes of differentiation state in both normal and malignant hematopoietic cells. To discover novel differentiation therapies, we applied this approach to analyze the gene expression profiles of HL-60 leukemia cells treated with a small molecule drug library. Among multiple drugs that significantly increased the LMIs, we identified mebendazole, an anti-helminthic clinically used for decades with no known significant toxicity. We tested the differentiation activity of mebendazole using primary leukemia blast cells isolated from human acute myeloid leukemia (AML) patients. We determined that treatment with mebendazole induces dramatic differentiation of leukemia blast cells as shown by cellular morphology and cell surface markers. Furthermore, mebendazole treatment significantly extended the survival of leukemia-bearing mice in a xenograft model. These findings suggest that mebendazole may be utilized as a low toxicity therapeutic for human acute myeloid leukemia and confirm the LMI approach as a robust tool for the discovery of novel differentiation therapies for cancer.