Pregnancy involves progressive relationship changes between conceptus-derived trophoblasts and maternal decidual vessels and leukocytes. Uterine natural killer (uNK) cells, the dominant leukocytes in early human and mouse decidua, have late gestational cardio-protective roles through mid-gestational initiation of decidual spiral arterial modification. The earlier gestational functions of uNK cells are unknown. Comparisons of gestation days (GD) 6.5–9.5 implant sites from allogeneically mated alymphoid or normal BALB/c mice (Rag2^−/−Il2rg^−/−; NK-T-B- versus +/+) by whole mount immunohistochemistry revealed delays in Rag2^−/−Il2rg^−/− uterine lumen closure, trophoblast invasion and conceptus development. Also delayed were onset of mesometrial angiogenesis and pruning of neo-vascular networks in decidua basalis. This phenotype was fully reversed in BALB/c-Rag2^−/−Il2rg^−/− pregnancies that followed adoptive Rag2^−/− (NK+B-T-) marrow transfer. These data suggest that uNK cells coordinate GD-appropriate phases of decidual angiogenesis, which in turn paces progressive changes in early implant sites that support normal fetal growth. Similar roles for human CD56^bright decidual NK cells could explain the importance of CD56^bright decidual NK cell activation to pregnancy success.