Differentiation of human endometrial stromal cells (HESC) into decidual cells represents a highly coordinated process essential for embryo implantation. We show that decidualizing HESC down-regulate the histone methyltransferase enhancer of Zeste homolog 2 (EZH2), resulting in declining levels of trimethylation of histone 3 on lysine 27 (H3K27me3) at the proximal promoters of key decidual marker genes PRL and IGFBP1. Loss of H3K27me3 was associated with a reciprocal enrichment in acetylation of the same lysine residue, indicating active remodeling from repressive to transcriptionally permissive chromatin. Chromatin immunoprecipitation coupled with DNA microarray analysis demonstrated that decidualization triggers genome-wide changes in H3K27me3 distribution that only partly overlap those observed upon EZH2 knockdown in undifferentiated HESC. Gene ontology revealed that gain of the repressive H3K27me3 mark in response to decidualization and upon EZH2 knockdown in undifferentiated cells was enriched at the promoter regions of genes involved in transcriptional regulation and growth/cell proliferation, respectively. However, loss of the H3K27me3 mark (indicating increased chromatin accessibility) in decidualizing cells and upon EZH2 knockdown occurred at selective loci enriched for genes functionally implicated in responses to stimulus. In agreement, EZH2 knockdown in undifferentiated HESC was sufficient to augment the induction of decidual marker genes in response to cyclic AMP and progesterone signaling. Thus, loss of EZH2-dependent methyltransferase activity in the endometrium is integral to the process of chromatin remodeling that enables the transition from a proliferative to a decidual phenotype in response to differentiation cues.