Adequate invasion of the human placenta during the first weeks of pregnancy is a critical step in ensuring both fetal and maternal health. A rapidly expanding body of evidence suggests that decidual natural killer (dNK) cells, a distinct population of CD56brightCD16- lymphocytes, are key regulators of this complex process. Experiments using murine models and in vitro evidence using human tissue cultures suggest that dNK cells modulate extravillous trophoblast (EVT) invasion and remodelling of maternal spiral arteries via both contact-dependent and contact-independent mechanisms. In addition, the differential expression of surface receptors by dNK cells may have a role in determining reproductive success through modulation of the maternal immune system at the time of implantation and placentation. The roles of cytokines, chemokines, and growth factors secreted by dNK cells and their influence on EVT migration, invasion, and pseudovasculogenesis are of particular interest. We reviewed the available experimental evidence related to the functional relationships between dNK cells and trophoblasts at the time of placentation to elucidate potential clinical correlations with human pathologies, including preeclampsia, recurrent pregnancy loss, IVF failure, and placenta accreta.