Transcription regulation involves enzyme-mediated changes in chromatin structure. Here, we describe a novel mode of histone crosstalk during gene silencing, in which histone H2A monoubiquitylation is coupled to the removal of histone H3 Lys 36 dimethylation (H3K36me2). This pathway was uncovered through the identification of dRING-associated factors (dRAF), a novel Polycomb group (PcG) silencing complex harboring the histone H2A ubiquitin ligase dRING, PSC and the F-box protein, and demethylase dKDM2. In vivo, dKDM2 shares many transcriptional targets with Polycomb and counteracts the histone methyltransferases TRX and ASH1. Importantly, cellular depletion and in vitro reconstitution assays revealed that dKDM2 not only mediates H3K36me2 demethylation but is also required for efficient H2A ubiquitylation by dRING/PSC. Thus, dRAF removes an active mark from histone H3 and adds a repressive one to H2A. These findings reveal coordinate trans-histone regulation by a PcG complex to mediate gene repression.