Abstract: The Anaphase Promoting Complex (APC), a large evolutionarily conserved ubiquitin-ligase complex, regulates cell cycle progression through mitosis and G1. Here, we present data suggesting APC-dependent cell cycle progression relies on a specific set of histone post-translational modifying enzymes. Multiple APC subunit mutants were impaired in total and modified histone H3 protein content. H3K56(Ac) levels were as reduced as total H3, indicating that loading histones with H3K56(Ac) is unaffected in APC mutants. However, under restrictive conditions, H3K9(Ac) and H3K79(me2) levels were further reduced compared to total H3. In a screen for histone acetyltransferase (HAT) and histone deacetylase (HDAC) mutants that genetically interact with the apc5(CA) mutant, we found that deletion of GCN5 or ELP3 severely hampered apc5(CA) temperature sensitive (ts) growth. Further analyses showed: i) the elp3Delta gcn5Delta double mutant ts defect was epistatic to that observed in apc5(CA) cells; ii) gcn5Delta and elp3Delta mutants accumulate in mitosis; and iii) turnover of the APC substrate, Clb2, is not impaired in elp3Delta gcn5Delta cells. Increased expression of ELP3, 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 elp3Delta gcn5Delta growth defects. Lastly, we demonstrate Gcn5 is unstable during G1, following G1 arrest, and is stabilized in APC mutants. We present our working model where Elp3/Gcn5 and the APC work together to facilitate passage through mitosis and G1. To progress into S, we propose that at least Gcn5 must then be targeted for degradation in an APC-dependent fashion.