Novel therapeutic strategies are needed to overcome cancer recurrence, metastasis, and resistance to chemo- and radiotherapy. Cancer stem cells (CSCs) are major contributors to the malignant transformation of cells due to their capacity for self-renewal. Although various CSC markers have been identified in several types of tumors, they are primarily used as cancer-prediction markers and for the isolation of CSC populations. CD133, one of the best-characterized CSC markers in distinct solid tumor types, was shown to be correlated with CSC tumor-initiating capacity; however, the regulation of CD133 expression and its function in cancer are poorly understood. Here, we show that CD133 expression is negatively regulated by direct binding of the p53 tumor suppressor protein to a noncanonical p53-binding sequence in the CD133 promoter. Binding of p53 recruits Histone Deacetylase 1 (HDAC1) to the CD133 promoter and subsequently suppresses CD133 expression by reducing histone H3 acetylation. Furthermore, CD133 depletion suppresses tumor cell proliferation, colony formation, and the expression of core stemness transcription factors including NANOG, octamer-binding transcription factor 4 (OCT4), SOX2, and c-MYC. Critically, the anti-proliferative effects of p53 are antagonized by rescue of CD133 expression in a p53 overexpressing cell line, indicating that the tumor suppressive activity of p53 might be mediated by CD133 suppression. Taken together, our results suggest that p53-mediated transcriptional regulation of CD133 is a key underlying mechanism for controlling the growth and tumor-initiating capacity of CSCs and provide a novel perspective on targeting CSCs for cancer therapy.