The presence of granulated lymphocytes in the human uterine mucosa, known as decidua during pregnancy, or endometrium otherwise, was first noted in the nineteenth century, but it was not until 1990 that these cells were identified as a type of natural killer (NK) cell. From the outset, uterine NK (uNK) cells were found to be less cytotoxic than their circulating counterparts, peripheral NK (pNK) cells. Recently, unbiased approaches have defined three subpopulations of uNK cells, all of which cluster separately from pNK cells. Here, we review the history of research into uNK cells, including their ability to interact with placental extravillous trophoblast cells and their potential role in regulating placental implantation. We go on to review more recent advances that focus on uNK cell development and heterogeneity and their potential to defend against infection and to mediate memory effects. Finally, we consider how a better understanding of these cells could be leveraged in the future to improve outcomes of pregnancy for mothers and babies.