Methylation of histone H3 K79 by Dot1L is a hallmark of actively transcribed genes that depends on monoubiquitination of H2B K120 (H2B-Ub) and is an example of histone modification cross-talk that is conserved from yeast to humans. We report here cryo-EM structures of Dot1L bound to ubiquitinated nucleosome that show how H2B-Ub stimulates Dot1L activity and reveal a role for the histone H4 tail in positioning Dot1L. We find that contacts mediated by Dot1L and the H4 tail induce a conformational change in the globular core of histone H3 that reorients K79 from an inaccessible position, thus enabling this side chain to insert into the active site in a position primed for catalysis. Our study provides a comprehensive mechanism of cross-talk between histone ubiquitination and methylation and reveals structural plasticity in histones that makes it possible for histone-modifying enzymes to access residues within the nucleosome core.