CD8+ T cells are the most frequent T cell population in the immune cell compartment at the feto-maternal interface. Due to their cytotoxic potential, the presence of CD8+ T cells in the immune privileged pregnant uterus has raised considerable interest. Here, we review our current understanding of CD8+ T cell biology in the uterus of pregnant women and discuss this knowledge in relation to a recently published immune cell Atlas of human decidua. We describe how the expansion of CD8+ T cells with an effector memory phenotype often presenting markers of exhaustion is critical for a successful pregnancy, and host defense towards pathogens. Moreover, we review new evidence on the presence of long-lasting immunological memory to former pregnancies and discuss its impact on prospective pregnancy outcomes. The formation of fetal-specific memory CD8+ T cell subests in the uterus, in particular of tissue resident, and stem cell memory cells requires further investigation, but promises interesting results to come. Advancing the knowledge of CD8+ T cell biology in the pregnant uterus will be pivotal for understanding not only tissue-specific immune tolerance but also the etiology of complications during pregnancy, thus enabling preventive or therapeutic interventions in the future.