ABSTRACT The anaphase-promoting complex (APC), a large evolutionarily conserved ubiquitin ligase complex, regulates cell cycle progression through mitosis and G 1 . Here, we present data suggesting that APC-dependent cell cycle progression relies on a specific set of posttranslational histone-modifying enzymes. Multiple APC subunit mutants were impaired in total and modified histone H3 protein content. Acetylated H3K56 (H3K56 Ac ) levels were as reduced as those of total H3, indicating that loading histones with H3K56 Ac is unaffected in APC mutants. However, under restrictive conditions, H3K9 Ac and dimethylated H3K79 (H3K79 me2 ) levels were more greatly reduced than those of total H3. In a screen for histone acetyltransferase (HAT) and histone deacetylase (HDAC) mutants that genetically interact with the apc5 CA (chromatin assembly) mutant, we found that deletion of GCN5 or ELP3 severely hampered apc5 CA temperature-sensitive (ts) growth. Further analyses showed that (i) the elp3 Δ gcn5 Δ double mutant ts defect was epistatic to that observed in apc5 CA cells; (ii) gcn5 Δ and elp3 Δ mutants accumulate in mitosis; and (iii) turnover of the APC substrate Clb2 is not impaired in elp3 Δ gcn5 Δ cells. Increased expression of ELP3 and GCN5 , as well as genes encoding the HAT Rtt109 and the chromatin assembly factors Msi1 and Asf1, suppressed apc5 CA defects, while increased APC5 expression partially suppressed elp3 Δ gcn5 Δ growth defects. Finally, we demonstrate that Gcn5 is unstable during G 1 and following G 1 arrest and is stabilized in APC mutants. We present our working model in which Elp3/Gcn5 and the APC work together to facilitate passage through mitosis and G 1 . To progress into S, we propose that at least Gcn5 must then be targeted for degradation in an APC-dependent fashion.