In yeast cells, the Rtf1 and Paf1 components of the Paf1 transcriptional elongation complex are important for recruitment of Set1, the histone H3-lysine 4 (H3-Lys4) methylase, to a highly localized domain at the 5' portion of active mRNA coding regions. Here, we show that Rtf1 is essential for global methylation of H3-Lys4 and H3-Lys79, but not H3-Lys36. This role of Rtf1 resembles that of Rad6, which mediates ubiquitination of histone H2B at lysine 123. Indeed, Rtf1 is required for H2B ubiquitination, suggesting that its effects on H3-Lys4 and H3-Lys79 methylation are an indirect consequence of its effect on H2B ubiquitination. Rtf1 is important for telomeric silencing, with loss of H3-Lys4 and H3-Lys79 methylation synergistically reducing Sir2 association with telomeric DNA. Dot1, the H3-Lys79 methylase, associates with transcriptionally active genes, but unlike the association of Set1 and Set2 (the H3-Lys36 methylase), this association is largely independent of Rtf1. We suggest that Rtf1 affects genome-wide ubiquitination of H2B by a mechanism that is distinct from its function as a transcriptional elongation factor.