Ubiquitin-mediated proteolysis of the replication licensing factor Cdt1 (Cdc10-dependent transcript 1) in S phase is a key mechanism that limits DNA replication to a single round per cell cycle in metazoans. In Xenopus egg extracts, Cdt1 is destroyed on chromatin during DNA replication. Here, we report that replication-dependent proteolysis of Cdt1 requires its interaction with proliferating cell nuclear antigen (PCNA), a homotrimeric processivity factor for DNA polymerases. Cdt1 binds to PCNA through a consensus PCNA-interaction motif that is conserved in Cdt1 of all metazoans, and removal of PCNA from egg extracts inhibits replication-dependent Cdt1 destruction. Mutation of the PCNA-interaction motif yields a stabilized Cdt1 protein that induces re-replication. DDB1, a component of the Cul4 E3 ubiquitin ligase that mediates human Cdt1 proteolysis in response to DNA damage, is also required for replication-dependent Cdt1 destruction. Cdt1 and DDB1 interact in extracts, and DDB1 chromatin loading is dependent on the binding of Cdt1 to PCNA, which indicates that PCNA docking activates the pre-formed Cdt1-Cul4(DDB1) ligase complex. Thus, PCNA functions as a platform for Cdt1 destruction, ensuring efficient and temporally restricted inactivation of a key cell-cycle regulator.