Balanced levels of histones are crucial for chromosome stability, and one major component of this control regulates histone mRNA amounts. The Saccharomyces cerevisiae poly(A) polymerases Trf4 and Trf5 are involved in a quality control mechanism that mediates polyadenylation and consequent degradation of various RNA species by the nuclear exosome. None of the known RNA targets, however, explains the fact that trf mutants have specific cell cycle defects consistent with a role in maintaining genome stability. Here, we investigate the role of Trf4/5 in regulation of histone mRNA levels. We show that loss of Trf4 and Trf5, or of Rrp6, a component of the nuclear exosome, results in elevated levels of transcripts encoding DNA replication-dependent histones. Suggesting that increased histone levels account for the phenotypes of trf mutants, we find that TRF4 shows synthetic genetic interactions with genes that negatively regulate histone levels, including RAD53. Moreover, synthetic lethality of trf4Delta rad53Delta is rescued by reducing histone levels whereas overproduction of histones is deleterious to trf's and rrp6Delta mutants. These results identify TRF4, TRF5, and RRP6 as new players in the regulation of histone mRNA levels in yeast. To our knowledge, the histone transcripts are the first mRNAs that are upregulated in Trf mutants.