The packaging of eukaryotic genomic DNA into chromatin is modulated through a range of posttranslational histone modifications. Among these, the role of histone ubiquitylation remains poorly understood. Here, we show that the essential Drosophila ubiquitin-specific protease 7 (USP7) contributes to epigenetic silencing of homeotic genes by Polycomb (Pc). We purified USP7 from embryo nuclear extracts as a stable heteromeric complex with guanosine 5′-monophosphate synthetase (GMPS). The USP7-GMPS complex catalyzed the selective deubiquitylation of histone H2B, but not H2A. Biochemical assays confirmed the tight association between USP7 and GMPS in Drosophila embryo extracts. Similar to USP7, mutations in GMPS acted as enhancers of Pc in vivo. USP7 binding to GMPS was required for histone H2B deubiquitylation and strongly augmented deubiquitylation of the human tumor suppressor p53. Thus, GMPS can regulate the activity of a ubiquitin protease. Collectively, these results implicate a biosynthetic enzyme in chromatin control via ubiquitin regulation.