In late mitosis and G1, a complex of the essential initiation proteins Mcm2-7 are assembled onto replication origins to 'license' them for initiation. At other times licensing is inhibited by cyclin-dependent kinases (CDKs) and geminin, thus ensuring that origins fire only once per cell cycle. Here we show that, paradoxically, CDKs are also required to inactivate geminin and activate the licensing system. On exit from metaphase in Xenopus laevis egg extracts, CDK-dependent activation of the anaphase-promoting complex (APC/C) results in the transient polyubiquitination of geminin. This ubiquitination triggers geminin inactivation without requiring ubiquitin-dependent proteolysis, and is essential for replication origins to become licensed. This reveals an unexpected role for CDKs and ubiquitination in activating chromosomal DNA replication.