BACKGROUND Tyrosine kinase inhibitors, such as imatinib, are not considered curative for chronic myeloid leukemia--regardless of the significant reduction of disease burden during treatment--since they do not affect the leukemic stem cells. However, the stochastic nature of hematopoiesis and recent clinical observations suggest that this view must be revisited. METHODS We studied the natural history of a large cohort of virtual patients with chronic myeloid leukemia under tyrosine kinase inhibitor therapy using a computational model of hematopoiesis and chronic myeloid leukemia that takes into account stochastic dynamics within the hematopoietic stem and early progenitor cell pool. RESULTS We found that in the overwhelming majority of patients the leukemic stem cell population undergoes extinction before disease diagnosis. Hence leukemic progenitors, susceptible to tyrosine kinase inhibitor attack, are the natural target for chronic myeloid leukemia treatment. Response dynamics predicted by the model closely match data from clinical trials. We further predicted that early diagnosis together with administration of tyrosine kinase inhibitor opens the path to eradication of chronic myeloid leukemia, leading to the wash out of the aberrant progenitor cells, ameliorating the patient's condition while lowering the risk of blast transformation and drug resistance. CONCLUSIONS Tyrosine kinase inhibitor therapy can cure chronic myeloid leukemia, although it may have to be prolonged. The depth of response increases with time in the vast majority of patients. These results illustrate the importance of stochastic effects on the dynamics of acquired hematopoietic stem cell disorders and have direct relevance for other hematopoietic stem cell-derived diseases.