A major challenge in biology is determining how evolutionarily novel characters originate; however, mechanistic explanations for the origin of new characters are almost completely unknown. The evolution of pregnancy is an excellent system in which to study the origin of novelties because mammals preserve stages in the transition from egg laying to live birth. To determine the molecular bases of this transition, we characterized the pregnant/gravid uterine transcriptome from tetrapods to trace the evolutionary history of uterine gene expression. We show that thousands of genes evolved endometrial expression during the origins of mammalian pregnancy, including genes that mediate maternal-fetal communication and immunotolerance. Furthermore, thousands of cis-regulatory elements that mediate decidualization and cell-type identity in decidualized stromal cells are derived from ancient mammalian transposable elements (TEs). Our results indicate that one of the defining mammalian novelties evolved from DNA sequences derived from ancient mammalian TEs co-opted into hormone-responsive regulatory elements distributed throughout the genome.