Methylation of histone H3K4 is a hallmark of actively transcribed genes that depends on mono-ubiquitination of histone H2B (H2B-Ub). H3K4 methylation in yeast is catalyzed by Set1, the methyltransferase subunit of COMPASS. We report here the cryo-EM structure of a six-protein core COMPASS subcomplex, which can methylate H3K4 and be stimulated by H2B-Ub, bound to a ubiquitinated nucleosome. Our structure shows that COMPASS spans the face of the nucleosome, recognizing ubiquitin on one face of the nucleosome and methylating H3 on the opposing face. As compared to the structure of the isolated core complex, Set1 undergoes multiple structural rearrangements to cement interactions with the nucleosome and with ubiquitin. The critical Set1 RxxxRR motif adopts a helix that mediates bridging contacts between the nucleosome, ubiquitin and COMPASS. The structure provides a framework for understanding mechanisms of trans-histone cross-talk and the dynamic role of H2B ubiquitination in stimulating histone methylation.