The five-subunit yeast Paf1 complex (Paf1C) regulates all stages of transcription and is critical for the monoubiquitylation of histone H2B (H2Bub), a modification that broadly influences chromatin structure and eukaryotic transcription. Here, we show that the histone modification domain (HMD) of Paf1C subunit Rtf1 directly interacts with the ubiquitin conjugase Rad6 and stimulates H2Bub independently of transcription. We present the crystal structure of the Rtf1 HMD and use site-specific, in vivo crosslinking to identify a conserved Rad6 interaction surface. Utilizing ChIP-exo analysis, we define the localization patterns of the H2Bub machinery at high resolution and demonstrate the importance of Paf1C in targeting the Rtf1 HMD, and thereby H2Bub, to its appropriate genomic locations. Finally, we observe HMD-dependent stimulation of H2Bub in a transcription-free, reconstituted in vitro system. Taken together, our results argue for an active role for Paf1C in promoting H2Bub and ensuring its proper localization in vivo.