Post-translational modification of the core histones represents an important level of epigenetic regulation of eukaryotic transcription. One such modification, the monoubiquitylation of histone H2B lysine 123 in yeast (H2B K123ub), is a well conserved mark implicated in activation of transcription, silencing of heterochromatic regions, establishment of other histone modifications, and regulation of development and differentiation in higher eukaryotes. The five-subunit yeast Paf1 complex (Paf1C), an important regulator of all stages of transcription, is required for the establishment of H2B K123ub, largely through the activity of its Rtf1 subunit. We have identified a 66-amino acid region in Rtf1, the Histone Modification Domain (HMD), which is capable of promoting H2B K123ub in vivo, even in a strain that lacks all Paf1C subunits. Aided by our crystal structure of the HMD, we constructed a large collection of HMD mutant strains and identified residues important for H2B K123ub, H3 K4 and H3 K79 methylation, and telomeric silencing. Guided by analysis of these mutants, we performed in vivo crosslinking experiments using the phenylalanine analog p-benzoyl-L-phenylalanine (BPA). Exposure of cells to ultraviolet radiation induced site-specific crosslinks with a short linker distance, allowing us to identify proteins directly interacting with the HMD. Among the collection of proteins that crosslinked to the HMD, we identified the ubiquitin conjugase for H2B K123 ubiquitylation, Rad6. The residues that crosslink to Rad6 lie along one face of an alpha helix within the HMD. Importantly, a mutation that inactivates the HMD eliminates the Rtf1-Rad6 crosslink. To further probe the functions of the Rtf1 HMD and the entire Paf1C, we have used ChIP-exo technology to map the occupancy of Paf1C subunits, as well as the isolated HMD and components of the H2B K123 machinery, with high resolution genome-wide. The results of these studies support the idea that Paf1C occupancy is dictated by its interactions with the RNA polymerase II elongation machinery, but the Rtf1 HMD localizes to histone H2B. Finally, using a minimal in vitro ubiquitylation assay, we have shown that the HMD stimulates the specific in vitro ubiquitylation activity of Rad6 in a manner that is dependent on the ubiquitin ligase Bre1. Collectively these results provide new mechanistic insight into the critical role of the highly conserved yeast Paf1C in establishing histone modifications during transcription elongation.