A successful pregnancy relies on immunological adaptations that allow the fetus to grow and develop in the uterus, despite being recognized by maternal immune cells. Among several immunocompetent cell types present within the human maternal/fetal interface, DC-SIGN(+) dendritic cells (DCs) and CD56(+) natural killer (NK) cells are of major importance for early pregnancy maintenance, not only generating maternal immunological tolerance but also regulating stromal cell differentiation. Previous reports show the presence of NK-DC cell conjugates in first trimester human decidua, suggesting that these cells may play a role in the modulation of the local immune response within the uterus. While effective immunity is necessary to protect the mother from harmful pathogens, some form of tolerance must be activated to avoid an immune response against fetal antigens. This review article discusses current evidence concerning the functions of DC and NK cells in pregnancy and their liaison in human decidua.