T-regulatory (Treg) cells are a specific subset of T cells that suppress immune responses and promote self immune tolerance. They are upregulated in the thymus and blood of humans and mice during pregnancy and are thought to play a critical role in protecting the semi-allograft fetus from the maternal immune system. Key to this process is the upregulation of forkhead box protein-3 (FOXP3), which contains a pioneer element or c-Rel binding motif within the non-coding 5’ region of the gene that is critical for thymic Treg expansion. To explore the evolution and molecular conservation of Treg mediated fetal-tolerance we sequenced FOXP3 in a marsupial, the tammar wallaby, and characterized expression in Ficoll-extracted lymphocytes during pregnancy. FOXP3 mRNA and protein expression was absent from lymphocyte RNA during pregnancy in the tammar wallaby but present in RNA pools from other tissues. We also screened the diverse genomes of mammals and non-mammalian vertebrates for the presence of the c-Rel binding motif at the FOXP3 locus. This sequence is conserved in the genomes of eutherian mammals but not in those of marsupials and non-mammalian vertebrates. Phylogenetic comparison of vertebrate FOXP3 sequences also shows differential evolution of this regulatory domain. The results provide the first evidence that Treg induced fetal-tolerance may be a unique adaptation of some mammals to support longer pregnancy or more invasive placentation.