The endometrium contains a distinct population of immune cells that undergo cyclic changes during the menstrual cycle and implantation. The majority of these leucocytes are uterine NK (uNK) cells, however how these cells interact with uterine stromal fibroblasts remains unclear. We therefore investigated the paracrine effect of medium conditioned by uterine decidual leucocytes (which are enriched for uNK cells) on the gene expression profile of endometrial stromal fibroblasts in vitro using a cDNA microarray. Our results, verified by real-time PCR, ELISA and FACS analysis, reveal that soluble factors from uterine leucocytes substantially alter endometrial stromal fibroblast gene expression. The largest group of up-regulated genes found was chemokines and cytokines. These include IL-8, CCL8 and CXCL1, which have also been shown to be stimulated by contact of stromal fibroblasts with trophoblast, suggesting that uNK cells work synergistically to support trophoblast migration during implantation. The decidual leucocytes also up-regulated IL-15 and IL-15Ralpha in stromal fibroblasts which could produce a niche for uNK cells allowing proliferation within and recruitment into the uterus, as seen in bone marrow. Overall this study demonstrates, for the first time, the paracrine communication between uterine leucocytes and uterine stromal fibroblasts, and adds to the understanding of how the uterine immune system contributes to the changes seen within the cycling endometrium.