Natural killer (NK) cells represent the most prominent immune cell type found in the uterus in the first trimester of human pregnancy and in the secretory phase of menstrual cycle. The role of NK cells in pregnancy has been largely discussed over the past years and it is now becoming increasingly clear that they may influence pregnancy outcome at several levels. In normal pregnancy, it appears that the major function of NK cells is to provide benefit by secreting a number of cytokines, chemokines and angiogenic factors rather than to exert a cytotoxic activity. However, the origin of decidual NK cells is still debated and it remains unclear whether they can derive from NK cell populations recruited from peripheral blood and/or other tissues or from self renewal of NK cell progenitors present in the uterus prior to pregnancy or recruited from other tissues. Here, we review the molecular mechanisms underlying peripheral blood NK cell recruitment and its role in the accumulation of NK cells in the decidua during early pregnancy.