A challenge of genome annotation is the identification of genes performing specific biological functions. Here, we propose a phylogenetic approach that utilizes RNA-seq data to infer the historical relationships among cell types and to trace the pattern of gene-expression changes on the tree. The hypothesis is that gene-expression changes coincidental with the origin of a cell type will be important for the function of the derived cell type. We apply this approach to the endometrial stromal cells (ESCs), which are critical for the initiation and maintenance of pregnancy. Our approach identified well-known regulators of ESCs, PGR and FOXO1, as well as genes not yet implicated in female fertility, including GATA2 and TFAP2C. Knockdown analysis confirmed that they are essential for ESC differentiation. We conclude that phylogenetic analysis of cell transcriptomes is a powerful tool for discovery of genes performing cell-type-specific functions.