Pregnancy presents an immunological conundrum because two genetically different individuals coexist. The maternal lymphocytes at the uterine maternal-fetal interface that can recognize mismatched placental cells are T cells and abundant distinctive uterine NK (uNK) cells. Multiple mechanisms exist that avoid damaging T cell responses to the fetus, whereas activation of uNK cells is probably physiological. Indeed, genetic epidemiological data suggest that the variability of NK cell receptors and their MHC ligands define pregnancy success; however, exactly how uNK cells function in normal and pathological pregnancy is still unclear, and any therapies aimed at suppressing NK cells must be viewed with caution. Allorecognition of fetal placental cells by uNK cells is emerging as the key maternal-fetal immune mechanism that regulates placentation.