The molecular mechanisms regulating leukemia-initiating cell (LIC) function are of important clinical significance. We use chronic myelogenous leukemia (CML), as a model of LIC-dependent malignancy and identify the interaction between the ubiquitin ligase Fbw7 and its substrate c-Myc as a regulator of LIC homeostasis. Deletion of Fbw7 leads to c-Myc overexpression, p53-dependent LIC-specific apoptosis and the eventual inhibition of tumor progression. Decrease of either c-Myc protein levels or attenuation of the p53 response rescues LIC activity and disease progression. Further experiments showed that Fbw7 expression is required for survival and maintenance of human CML LIC. These studies identify a ubiquitin ligase:substrate pair regulating LIC activity, suggesting that targeting of the Fbw7:c-Myc axis is an attractive therapy target in refractory CML.