The pentaspan membrane glycoprotein CD133 marks lineage-specific cancer progenitor cells and is associated with poor prognosis in a number of tumor types. Despite its utility as a cancer progenitor cell marker, CD133 protein regulation and molecular function remain poorly understood. We find that the deacetylase HDAC6 physically associates with CD133 to negatively regulate CD133 trafficking down the endosomal-lysosomal pathway for degradation. We further demonstrate that CD133, HDAC6, and the central molecule of the canonical Wnt signaling pathway, β-catenin, can physically associate as a ternary complex. This association stabilizes β-catenin via HDAC6 deacetylase activity, which leads to activation of β-catenin signaling targets. Downregulation of either CD133 or HDAC6 results in increased β-catenin acetylation and degradation, which correlates with decreased proliferation in vitro and tumor xenograft growth in vivo. Given that CD133 marks progenitor cells in a wide range of cancers, targeting CD133 may be a means to treat multiple cancer types.