Organismal function is, to a great extent, determined by interactions among their fundamental building blocks, the cells. In this work, we studied the cell-cell interactome of fetal placental trophoblast cells and maternal endometrial stromal cells, using single-cell transcriptomics. The placental interface mediates the interaction between two semiallogenic individuals, the mother and the fetus, and is thus the epitome of cell interactions. To study these, we inferred the cell-cell interactome by assessing the gene expression of receptor-ligand pairs across cell types. We find a highly cell-type-specific expression of G-protein-coupled receptors, implying that ligand-receptor profiles could be a reliable tool for cell type identification. Furthermore, we find that uterine decidual cells represent a cell-cell interaction hub with a large number of potential incoming and outgoing signals. Decidual cells differentiate from their precursors, the endometrial stromal fibroblasts, during uterine preparation for pregnancy. We show that decidualization (even in vitro) enhances the ability to communicate with the fetus, as most of the receptors and ligands up-regulated during decidualization have their counterpart expressed in trophoblast cells. Among the signals transmitted, growth factors and immune signals dominate, and suggest a delicate balance of enhancing and suppressive signals. Finally, this study provides a rich resource of gene expression profiles of term intravillous and extravillous trophoblasts, including the transcriptome of the multinucleated syncytiotrophoblast.