Histone modifications, including H3 K56 acetylation, have been implicated in DNA damage tolerance. Here, we present evidence that Hst3 and Hst4, two paralogues of the histone deacetylase Sir2, target the cell cycle-regulated acetylation of H3 on K56 and are downregulated during DNA damage in a checkpoint-dependent manner. We show that Hst3 and Hst4 are themselves cell cycle regulated and that their misexpression affects H3 K56-Ac. Moreover, a histone H3 K56R mutation is epistatic to all phenotypes caused by HST3/4 deletion or HST3 overexpression, suggesting that H3K56-Ac is the major target of these histone deacetylases. On examining 18 members of the "Clb2 cluster" of cell cycle-regulated proteins to which Hst3 belongs, we find that two others, Ynl058c and Alk1, are significantly downregulated on DNA damage. Taken together, our data show that Hst3/Hst4 are negative regulators of H3 K56-Ac and that HST3 downregulation by a checkpoint-mediated transcriptional repression system is essential for surviving DNA damage.