Methylation of histone H3 lysine 36 (H3K36me) by yeast Set2 is critical for the maintenance of chromatin structure and transcriptional fidelity. However, we do not know the full range of Set2/H3K36me functions or the scope of mechanisms that regulate Set2-dependent H3K36 methylation. Here, we show that the APC/CCDC20 complex regulates Set2 protein abundance during the cell cycle. Significantly, absence of Set2-mediated H3K36me causes a loss of cell cycle control and pronounced defects in the transcriptional fidelity of cell cycle regulatory genes, a class of genes that are generally long, hence highly dependent on Set2/H3K36me for their transcriptional fidelity. Because APC/C also controls human SETD2, and SETD2 likewise regulates cell cycle progression, our data imply an evolutionarily conserved cell cycle function for Set2/SETD2 that may explain why recurrent mutations of SETD2 contribute to human disease.