Pluripotent cells of the mammalian embryo undergo extensive chromatin rewiring to prepare for lineage commitment after implantation. Repressive H3K27me3, deposited by Polycomb Repressive Complex 2 (PRC2), is reallocated from large blankets in pre-implantation embryos to mark promoters of developmental genes. The regulation of this global redistribution of H3K27me3 is poorly understood. Here we report a post-translational mechanism that destabilizes PRC2 to constrict H3K27me3 during lineage commitment. Using an auxin-inducible degron system, we show that the deubiquitinase Usp9x is required for mouse embryonic stem (ES) cell self-renewal. Usp9x-high ES cells have high PRC2 levels and bear a chromatin and transcriptional signature of the pre-implantation embryo, whereas Usp9x-low ES cells resemble the post-implantation, gastrulating epiblast. We show that Usp9x interacts with, deubiquitinates and stabilizes PRC2. Deletion of Usp9x in post-implantation embryos results in the derepression of genes that normally gain H3K27me3 after gastrulation, followed by the appearance of morphological abnormalities at E9.5, pointing to a recurrent link between Usp9x and PRC2 during development. Usp9x is a marker of "stemness" and is mutated in various neurological disorders and cancers. Our results unveil a Usp9x-PRC2 regulatory axis that is critical at peri-implantation and may be redeployed in other stem cell fate transitions and disease states.