The forkhead box M1 (FoxM1) transcription factor is overexpressed in many cancers, and in mouse models it is required for tumor progression. FoxM1 activates expression of the cell cycle genes required for both S and M phase progression. Here we demonstrate that FoxM1 is degraded in late mitosis and early G1 phase by the anaphase-promoting complex/cyclosome (APC/C) E3 ubiquitin ligase. FoxM1 interacts with the APC/C complex and its adaptor, Cdh1. Expression of Cdh1 stimulated degradation of the FoxM1 protein, and depletion of Cdh1 resulted in stabilization of the FoxM1 protein in late mitosis and in early G1 phase of the cell cycle. Cdh1 has been implicated in regulating S phase entry. We show that codepletion of FoxM1 inhibits early S phase entry observed in Cdh1-depleted cells. The N-terminal region of FoxM1 contains both destruction box (D box) and KEN box sequences that are required for targeting by Cdh1. Mutation of either the D box sequence or the KEN box sequence stabilized FoxM1 and blocked Cdh1-induced proteolysis. Cells expressing a nondegradable form of FoxM1 entered S phase rapidly following release from M phase arrest. Together, our observations show that FoxM1 is one of the targets of Cdh1 in late M or early G1 phase and that its proteolysis is important for regulated entry into S phase.