Among animal species, cell types vary greatly in terms of number and kind. The number of cell types found within an organism differs considerably between species, and cell type diversity is a significant contributor to differences in organismal structure and function. These observations suggest that cell type origination is a significant source of evolutionary novelty. The molecular mechanisms that result in the evolution of novel cell types, however, are poorly understood. Here, we show that a novel cell type of eutherians mammals, the decidual stromal cell (DSC), evolved by rewiring an ancestral cellular stress response. We isolated the precursor cell type of DSCs, endometrial stromal fibroblasts (ESFs), from the opossum Monodelphis domestica. We show that, in opossum ESFs, the majority of decidual core regulatory genes respond to decidualizing signals but do not regulate decidual effector genes. Rather, in opossum ESFs, decidual transcription factors function in apoptotic and oxidative stress response. We propose that rewiring of cellular stress responses was an important mechanism for the evolution of the eutherian decidual cell type.