An effective bidirectional communication between an implantation-competent blastocyst and the receptive uterus is a prerequisite for mammalian reproduction. The blastocyst will implant only when this molecular cross-talk is established. Here we show that the muscle segment homeobox gene (Msh) family members Msx1 and Msx2, which are two highly conserved genes critical for epithelial-mesenchymal interactions during development, also play crucial roles in embryo implantation. Loss of Msx1/Msx2 expression correlates with altered uterine luminal epithelial cell polarity and affects E-cadherin/β-catenin complex formation through the control of Wnt5a expression. Application of Wnt5a in vitro compromised blastocyst invasion and trophoblast outgrowth on cultured uterine epithelial cells. The finding that Msx1/Msx2 genes are critical for conferring uterine receptivity and readiness to implantation could have clinical significance, because compromised uterine receptivity is a major cause of pregnancy failure in IVF programs.