Mammalian pregnancy involves tremendous de novo maternal vascular construction to adequately support conceptus development. In early mouse decidua basalis (DB), maternal uterine natural killer (uNK) cells oversee this process directing various aspects during the formation of supportive vascular networks. The uNK cells recruited to early implantation site DB secrete numerous factors that act in the construction of early decidual vessels (neoangiogenesis) as well as in the alteration of the structural components of newly developing and existing vessels (pruning and remodeling). Although decidual and placental development sufficient to support live births occur in the absence of normally functioning uNK cells, development and structure of implantation site are optimized through the presence of normally activated uNK cells. Human NK cells are also recruited to early decidua. Gestational complications including recurrent spontaneous abortion, fetal growth restriction, preeclampsia, and preterm labor are linked with the absence of human NK cell activation via paternally inherited conceptus transplantation antigens. This review summarizes the roles that mouse uNK cells normally play in decidual neoangiogenesis and spiral artery remodeling in mouse pregnancy and briefly discusses changes in early developmental angiogenesis due to placental growth factor deficiency.