Implantation and placentation present an immune challenge because of the semi-allogeneic nature of the conceptus. In this review, histological evidence for maternal immune cellular responses at the implantation site is summarized. Decidualization of the endometrium itself has features in common with an inflammatory response. During decidualization, infiltration by uterine natural killer (NK) cells occurs, and these interact with the non-polymorphic human leukocyte antigen (HLA) class I antigens expressed by invading extravillous trophoblasts. In humans, extension of trophoblast invasion beyond the decidual layer into the myometrium presents an additional challenge, which might be relevant for pregnancy complications such as pre-eclampsia. How far maternal cellular responses to invading trophoblasts seen at later stages of pregnancy can be traced back to the implantation period is an open question.