Recruitment of the Polycomb repressive complexes PRC1 and PRC2 by Xist RNA is an important paradigm for chromatin regulation by long noncoding RNAs. Here, we show that the noncanonical Polycomb group RING finger 3/5 (PCGF3/5)–PRC1 complex initiates recruitment of both PRC1 and PRC2 in response to Xist RNA expression. PCGF3/5–PRC1–mediated ubiquitylation of histone H2A signals recruitment of other noncanonical PRC1 complexes and of PRC2, the latter leading to deposition of histone H3 lysine 27 methylation chromosome-wide. Pcgf3/5 gene knockout results in female-specific embryo lethality and abrogates Xist-mediated gene repression, highlighting a key role for Polycomb in Xist-dependent chromosome silencing. Our findings overturn existing models for Polycomb recruitment by Xist RNA and establish precedence for H2AK119u1 in initiating Polycomb domain formation in a physiological context.