The mammalian Msx homeobox genes, Msx1 and Msx2, encode transcription factors that control organogenesis and tissue interactions during embryonic development. We observed overlapping expression of these factors in uterine epithelial and stromal compartments of pregnant mice prior to embryo implantation. Conditional ablation of both Msx1 and Msx2 in the uterus resulted in female infertility due to a failure in implantation. In these mutant mice (Msx1/2(d/d)), the uterine epithelium exhibited persistent proliferative activity and failed to attach to the embryos. Gene expression profiling of uterine epithelium and stroma of Msx1/2(d/d) mice revealed an elevated expression of several members of the Wnt gene family in the preimplantation uterus. Increased canonical Wnt signaling in the stromal cells activated β-catenin, stimulating the production of a subset of fibroblast growth factors (FGFs) in these cells. The secreted FGFs acted in a paracrine manner via the FGF receptors in the epithelium to promote epithelial proliferation, thereby preventing differentiation of this tissue and creating a non-receptive uterus refractory to implantation. Collectively, these findings delineate a unique signaling network, involving Msx1/2, Wnts, and FGFs, which operate in the uterus at the time of implantation to control the mesenchymal-epithelial dialogue critical for successful establishment of pregnancy.