The class II Histone deacetylase (HDAC), HDAC4, is expressed in a tissue-specific manner, and it represses differentiation of specific cell types. We demonstrate here that HDAC4 is expressed in the proliferative zone in small intestine and colon and that its expression is down-regulated during intestinal differentiation in vivo and in vitro. Subcellular localization studies demonstrated HDAC4 expression was predominantly nuclear in proliferating HCT116 cells and relocalized to the cytoplasm after cell cycle arrest. Down-regulating HDAC4 expression by small interfering RNA (siRNA) in HCT116 cells induced growth inhibition and apoptosis in vitro, reduced xenograft tumor growth, and increased p21 transcription. Conversely, overexpression of HDAC4 repressed p21 promoter activity. p21 was likely a direct target of HDAC4, because HDAC4 down-regulation increased p21 mRNA when protein synthesis was inhibited by cycloheximide. The importance of p21 repression in HDAC4-mediated growth promotion was demonstrated by the failure of HDAC4 down-regulation to induce growth arrest in HCT116 p21-null cells. HDAC4 down-regulation failed to induce p21 when Sp1 was functionally inhibited by mithramycin or siRNA-mediated down-regulation. HDAC4 expression overlapped with that of Sp1, and a physical interaction was demonstrated by coimmunoprecipitation. Chromatin immunoprecipitation (ChIP) and sequential ChIP analyses demonstrated Sp1-dependent binding of HDAC4 to the proximal p21 promoter, likely directed through the HDAC4–HDAC3–N-CoR/SMRT corepressor complex. Consistent with increased transcription, HDAC4 or SMRT down-regulation resulted in increased histone H3 acetylation at the proximal p21 promoter locus. These studies identify HDAC4 as a novel regulator of colon cell proliferation through repression of p21.