Monomethylated histone H4 lysine 20 (H4K20me1) is tightly regulated during the cell cycle. The H4K20me1 demethylase PHF8 transcriptionally regulates many cell cycle genes and is therefore predicted to play key roles in the cell cycle. Here, we show that PHF8 protein levels are the highest during G2 phase and mitosis, and we found PHF8 protein stability to be regulated by the ubiquitin-proteasome system. Purification of the PHF8 complex led to the identification of many subunits of the anaphase-promoting complex (APC) associated with PHF8. We showed that PHF8 interacts with the CDC20-containing APC (APC(cdc20)) primarily during mitosis. In addition, we defined a novel, KEN- and D-box-independent, LXPKXLF motif on PHF8 that is required for binding to CDC20. Through various in vivo and in vitro assays, we demonstrate that mutations of the LXPKXLF motif abrogate polyubiquitylation of PHF8 by the APC. APC substrates are typically cell cycle regulators, and consistent with this, the loss of PHF8 leads to prolonged G2 phase and defective mitosis. Furthermore, we provide evidence that PHF8 plays an important role in transcriptional activation of key G2/M genes during G2 phase. Taken together, these findings suggest that PHF8 is regulated by APC(cdc20) and plays an important role in the G2/M transition.