Abstract: The proteasome regulates histone lysine methylation and gene transcription, but how it does so is poorly understood. To better understand this process, we used the epistatic miniarray profile (E-MAP) approach to identify factors that genetically interact with proteasomal subunits. In addition to members of the Set1 complex that mediate histone H3 lysine 4 methylation (H3K4me), we found that deleting members of the CCR4/NOT mRNA processing complex exhibit synthetic phenotypes when combined with proteasome mutants. Further biochemical analyses revealed physical associations between CCR4/NOT and the proteasome in vivo. Consistent with the genetic and biochemical interactions linking CCR4/NOT with proteasome and Set1-mediated methylation, we find that loss of Not4 decreases global and gene-specific H3K4 trimethylation (H3K4me3) and decreases 19S proteasome recruitment to the PMA1 gene. Similar to proteasome regulation of histone methylation, loss of CCR4/NOT members does not affect ubiquitinated H2B. Mapping of Not4 identified the RING finger domain as essential for H3K4me3, suggesting a role for ubiquitin in this process. Consistent with this idea, loss of the Not4-interacting protein Ubc4, a known ubiquitin-conjugating enzyme, decreases H3K4me3. These studies implicate CCR4/NOT in the regulation of H3K4me3 through a ubiquitin-dependent pathway that likely involves the proteasome.