Replication licensing is carefully regulated to restrict replication to once in a cell cycle. In higher eukaryotes, regulation of the licensing factor Cdt1 by proteolysis and Geminin is essential to prevent re-replication. We show here that the N-terminal 100 amino acids of human Cdt1 are recognized for proteolysis by two distinct E3 ubiquitin ligases during S-G2 phases. Six highly conserved amino acids within the 10 first amino acids of Cdt1 are essential for DDB1-Cul4-mediated proteolysis. This region is also involved in proteolysis following DNA damage. The second E3 is SCF-Skp2, which recognizes the Cy-motif-mediated Cyclin E/A-cyclin-dependent kinase-phosphorylated region. Consistently, in HeLa cells cosilenced of Skp2 and Cul4, Cdt1 remained stable in S-G2 phases. The Cul4-containing E3 is active during ongoing replication, while SCF-Skp2 operates both in S and G2 phases. PCNA binds to Cdt1 through the six conserved N-terminal amino acids. PCNA is essential for Cul4- but not Skp2-directed degradation during DNA replication and following ultraviolet-irradiation. Our data unravel multiple distinct pathways regulating Cdt1 to block re-replication.