Evolution of the immune system is a key for efficient defense of the host against pathogens. At the same time unwanted immune response against self, needs to be tightly regulated to avoid catastrophic autoimmunity. While self-reactive thymocytes could be eliminated through a cell intrinsic mechanism termed “central tolerance”, an additional mechanism of immune regulation by the so called regulatory T cells (Treg cells) has become a major focus of immune research in recent years. Treg cells are a specific subtype of CD4+ lymphocytes absolutely critical for suppressing autoimmunity and uncontrolled immune response against pathogens. Furthermore, in tumor Treg cells are capable of dampening anti-tumor immunity, making them an attractive therapeutic target. The X-chromosome encoded transcription factor Foxp3, a hallmark of Treg cells, is responsible for establishing a unique transcriptional program that functionally and phenotypically distinguishes them from all other T cell lineages. However, despite its unequivocal role in Treg biology, the molecular basis of Foxp3’s function has only begun to emerge. To gain insights into the molecular mechanisms of Foxp3 mediated regulation of gene expression we purified Foxp3 transcriptional complexes and explored their composition. The biochemical and mass-spectrometric analyses revealed that Foxp3 forms multiprotein complexes of 400-800 kDa or larger and identified 361 associated proteins, ~30% of which are involved in the regulation of transcription. Notably, Foxp3 binds and directly regulates expression of a large proportion of the genes that serve as its co-factors. In reciprocation, some of the sequence-specific transcription factors that serve as Foxp3 binding partners facilitate Foxp3 expression. Functional analysis of Foxp3 cooperation with at least two of its associated partners provides further evidence for a cooperative network of transcriptional regulation afforded by Foxp3 and its associates to control distinct aspects of Treg cell biology.