Tumor recurrence following treatment remains a major clinical challenge. Evidence from xenograft models and human trials indicates selective enrichment of cancer-initiating cells (CICs) in tumors that survive therapy. Together with recent reports showing that CIC gene signatures influence patient survival, these studies predict that targeting self-renewal, the key 'stemness' property unique to CICs, may represent a new paradigm in cancer therapy. Here we demonstrate that tumor formation and, more specifically, human colorectal CIC function are dependent on the canonical self-renewal regulator BMI-1. Downregulation of BMI-1 inhibits the ability of colorectal CICs to self-renew, resulting in the abrogation of their tumorigenic potential. Treatment of primary colorectal cancer xenografts with a small-molecule BMI-1 inhibitor resulted in colorectal CIC loss with long-term and irreversible impairment of tumor growth. Targeting the BMI-1-related self-renewal machinery provides the basis for a new therapeutic approach in the treatment of colorectal cancer.