Immune homeostasis is dependent on tight control over the size of a population of regulatory T (T_reg) cells capable of suppressing over-exuberant immune responses. The T_reg cell subset is comprised of cells that commit to the T_reg lineage by upregulating the transcription factor Foxp3 either in the thymus (tT_reg) or in the periphery (iT_reg)^,. Considering a central role for Foxp3 in T_reg cell differentiation and function^,, we proposed that conserved non-coding DNA sequence (CNS) elements at the Foxp3 locus encode information defining the size, composition and stability of the T_reg cell population. Here we describe the function of three Foxp3 CNS elements (CNS1–3) in T_reg cell fate determination in mice. The pioneer element CNS3, which acts to potently increase the frequency of T_reg cells generated in the thymus and the periphery, binds c-Rel in in vitro assays. In contrast, CNS1, which contains a TGF-β–NFAT response element, is superfluous for tT_reg cell differentiation, but has a prominent role in iT_reg cell generation in gut-associated lymphoid tissues. CNS2, although dispensable for Foxp3 induction, is required for Foxp3 expression in the progeny of dividing T_reg cells. Foxp3 binds to CNS2 in a Cbf-β–Runx1 and CpG DNA demethylation-dependent manner, suggesting that Foxp3 recruitment to this ‘cellular memory module’ facilitates the heritable maintenance of the active state of the Foxp3 locus and, therefore, T_reg lineage stability. Together, our studies demonstrate that the composition, size and maintenance of the T_reg cell population are controlled by Foxp3 CNS elements engaged in response to distinct cell-extrinsic or -intrinsic cues.