Acetylation of histone H3 on lysine 56 occurs during mitotic and meiotic S phase in fungal species. This acetylation blocks a direct electrostatic interaction between histone H3 and nucleosomal DNA, and the absence of this modification is associated with extreme sensitivity to genotoxic agents. We show here that H3-K56 acetylation is catalyzed when Rtt109, a protein that lacks significant homology to known acetyltransferases, forms an active complex with either of two histone binding proteins, Asf1 or Vps75. Rtt109 binds to both these cofactors, but not to histones alone, forming enzyme complexes with kinetic parameters similar to those of known histone acetyltransferase (HAT) enzymes. Therefore, H3-K56 acetylation is catalyzed by a previously unknown mechanism that requires a complex of two proteins: Rtt109 and a histone chaperone. Additionally, these complexes are functionally distinct, with the Rtt109/Asf1 complex, but not the Rtt109/Vps75 complex, being critical for resistance to genotoxic agents.