Efficient transcription is linked to modification of chromatin. For instance, tri-methylation of lysine 4 on histone H3 (H3K4) strongly correlates with transcriptional activity and is regulated by the Bur1/2 kinase complex. We found that the evolutionarily conserved Ccr4-Not complex is involved in establishing H3K4 tri-methylation in Saccharomyces cerevisiae. We observed synthetic lethal interactions of Ccr4-Not components with BUR1 and BUR2. Further analysis indicated that the genes encoding the Not-proteins are essential for efficient regulation of H3K4me3, but not H3K4me1/2, H3K36me2 or H3K79me2/3 levels. Moreover, regulation of H3K4me3 levels by NOT4 is independent of defects in RNA polymerase II loading. We found NOT4 to be important for ubiquitylation of histone H2B via recruitment of the PAF complex, but not for recruitment or activation of the Bur1/2 complex. These results suggest a mechanism in which the Ccr4-Not complex functions parallel to or downstream of the Bur1/2 kinase to facilitate H3K4me3 via PAF complex recruitment.