Cyclin-dependent kinases (CDKs) restrict DNA replication origin firing to once per cell cycle by preventing the assembly of prereplicative complexes (pre-RCs; licensing) outside of G1 phase. Paradoxically, under certain circumstances, CDKs such as cyclin E-cdk2 are also required to promote licensing. Here, we show that CDK phosphorylation of the essential licensing factor Cdc6 stabilizes it by preventing its association with the anaphase promoting complex/cyclosome (APC/C). APC/C-dependent Cdc6 proteolysis prevents pre-RC assembly in quiescent cells and, when cells reenter the cell cycle from quiescence, CDK-dependent Cdc6 stabilization allows Cdc6 to accumulate before the licensing inhibitors geminin and cyclin A which are also APC/C substrates. This novel mechanism for regulating protein stability establishes a window of time prior to S phase when pre-RCs can assemble which we propose represents a critical function of cyclin E.