The essential histone H3 lysine 79 methyltransferase Dot1L regulates transcription and genomic stability and is deregulated in leukemia. The activity of Dot1L is stimulated by mono-ubiquitination of histone H2B on lysine 120 (H2BK120Ub); however, the detailed mechanism is not understood. We report cryo-EM structures of human Dot1L bound to (1) H2BK120Ub and (2) unmodified nucleosome substrates at 3.5 Å and 4.9 Å, respectively. Comparison of both structures, complemented with biochemical experiments, provides critical insights into the mechanism of Dot1L stimulation by H2BK120Ub. Both structures show Dot1L binding to the same extended surface of the histone octamer. In yeast, this surface is used by silencing proteins involved in heterochromatin formation, explaining the mechanism of their competition with Dot1. These results provide a strong foundation for understanding conserved crosstalk between histone modifications found at actively transcribed genes and offer a general model of how ubiquitin might regulate the activity of chromatin enzymes. Valencia-Sánchez et al. provide structural and functional explanations of how H2BK120Ub stimulates Dot1L methyltranferase activity and show that ubiquitin binding reduces Dot1L mobility on the nucleosome, allowing efficient methylation of H3K79. Given the abnormal methylation of H3K79 in MLL-rearranged leukemia, these findings open new avenues to develop therapies modulating Dot1L activity.