Foxp3 and its protein partners establish a regulatory T (Treg) cell transcription profile and promote immunological tolerance. However, molecular features contributing to a Treg-specific gene expression program are still incompletely understood. We find that the transcription factor Bcl11b is a prominent Foxp3 cofactor with multifaceted functions in Treg biology. Optimal genomic recruitment of Foxp3 and Bcl11b is critically interdependent. Genome-wide occupancy studies coupled with gene expression profiling reveal that Bcl11b, in association with Foxp3, is primarily responsible in establishing a Treg-specific gene activation program. Furthermore, Bcl11b restricts misdirected recruitment of Foxp3 to sites, which would otherwise result in an altered Treg transcriptome profile. Consequently, Treg-specific ablation of Bcl11b results in marked breakdown of immune tolerance, leading to aggressive systemic autoimmunity. Our study provides previously underappreciated mechanistic insights into molecular events contributing to basic aspects of Treg function. Furthermore, it establishes a therapeutic target with potential implications in autoimmunity and cancer.