During the establishment of pregnancy, a human blastocyst implants into the uterine endometrium to facilitate the formation of a functional placenta. Implantation involves the blastocyst adhering to the uterine luminal epithelium before the primitive syncytiotrophoblast and subsequently specialised cells, the extravillous trophoblast (EVT), invade into the decidua in order to engraft and remodel uterine spiral arteries, creating the placental blood supply at the end of the first trimester. Defects in EVT invasion lead to abnormal placentation and thus adverse pregnancy outcomes. The local decidual environment is thought to play a key role in regulating trophoblast invasion. Here we describe the major cell types present in the decidua during the first trimester of pregnancy and review what is known about their regulation of EVT invasion. Overall, the evidence suggests that in a healthy pregnancy almost all cell types in the decidua actively promote EVT invasion and, further, that reduced EVT invasion towards the end of the first trimester is regulated, in part, by the reduced invasive capacity of EVTs shown at this time.