The decidual-placental interface is one of the most diverse and rapidly evolving tissues in mammals. Its origin as a chimeric fetal-maternal tissue poses a unique evolutionary puzzle. We present single-cell RNA sequencing atlases from the fetal-maternal interfaces of the opossum, a marsupial, the Malagasy common tenrec, an afrotherian with primitive reproductive features, and mouse, guinea pig, and human. Invasive trophoblast shares a common transcriptomic signature across eutherians, which we argue represents a cell type family that radiated following the evolution of hemochorial placentation. We find evidence that the eutherian decidual stromal cell evolved stepwise from a predecidual state retained in Tenrec , followed by a second decidual cell type originating in Boreoeutheria with endocrine characteristics. We reconstruct ligand-receptor signaling to test evolutionary hypotheses at scale. Novel trophoblast and decidual cell types display strong integration into signaling networks compared to other cells. Additionally, we find consistent disambiguation between fetal and maternal signaling. Using phylogenetic analysis, we infer the cell-cell signaling network of the Placental common ancestor, and identify increased rates of signaling evolution in Euarchontoglires. Together, our findings reveal novel cell type identities and cell signaling dynamics at the mammalian fetal-maternal interface.