Runx2 (Cbfa1, AML-3) is multifunctional transcription factor that is essential for osteoblast development. Runx2 binds specific DNA sequences and interacts with transcriptional coactivators and corepressors to either activate or repress transcription of tissue-specific genes. In this study, the p21 CIP/WAF1 promoter was identified as a repressible target of Runx2. A carboxy-terminal repression domain distinct from the well-characterized TLE/Groucho-binding domain contributed to Runx2-mediated p21 repression. This carboxy-terminal domain was sufficient to repress a heterologous GAL reporter. The repressive activity of this domain was sensitive to the histone deacetylase inhibitor trichostatin A but not to trapoxin B. HDAC6, which is insensitive to trapoxin B, specifically interacted with the carboxy terminus of Runx2. The HDAC6 interaction domain of Runx2 was mapped to a region overlapping the nuclear matrix-targeting signal. The Runx2 carboxy terminus was necessary for recruitment of HDAC6 from the cytoplasm to chromatin. HDAC6 also colocalized and coimmunoprecipitated with the nuclear matrix-associated protein Runx2 in osteoblasts. Finally, we show that HDAC6 is expressed in differentiating osteoblasts and that the Runx2 carboxy terminus is necessary for maximal repression of the p21 promoter in preosteoblasts. These data identify Runx2 as the first transcription factor to interact with HDAC6 and suggest that HDAC6 may bind to Runx2 in differentiating osteoblasts to regulate tissue-specific gene expression.