Colorectal tumor-initiating cells (CT-ICs) have self-renewal capabilities and have an important role in tumorigenesis, metastasis, recurrence and treatment resistance in colorectal cancer. Multiple cell-surface molecules targeting CT-ICs, possibly representing different CT-IC subpopulations, have been reported. However, whether new surface markers exist, as well as the mechanisms by which the markers regulate self-renewal, remain unclear. In this study, we enriched a CT-IC population through a serum-free low-adhesion system in vitro. Within this population, we found that CD58 and CD44 were upregulated using a cDNA GeneChip, and CD44(high)CD58(high) cancer cells, the common existence of which was demonstrated by flow cytometry in multiple colon cancer cell lines and primary specimens, exhibited enhanced self-renewal ability, epithelial-mesenchymal transition ability and tumorigenicity, both in vitro and in vivo. Furthermore, activated CD58 upregulated the Wnt/β-catenin pathway and thus promoted self-renewal of CT-ICs; conversely, knockdown of CD58 significantly impaired sphere formation and tumor growth. With immunoprecipitation and western blotting approaches, CD58 was found to upregulate the Wnt pathway by degradation of Dickkopf 3. These results indicate that CD58 is a novel cell-surface marker that functionally regulates self-renewal of CT-ICs, which may provide an intriguing therapeutic target for the efficient killing and elimination of CT-ICs.