The lineage factor Foxp3 is essential for the development and maintenance of regulatory T cells, but little is known about the mechanisms involved. Here, we demonstrate that an N-terminal proline-rich interaction region is crucial for Foxp3's function. Subdomains within this key region link Foxp3 to several independent mechanisms of transcriptional regulation. Our study suggests that Foxp3, even in the absence of its DNA-binding forkhead domain, acts as a bridge between DNA-binding interaction partners and proteins with effector function permitting it to regulate a large number of genes. We show that, in one such mechanism, Foxp3 recruits class I histone deacetylases to the promoters of target genes, counteracting activation-induced histone acetylation and thereby suppressing their expression.