Substrates of the E3 ubiquitin ligase CRL4(Cdt2), including Cdt1 and p21, contain a PCNA-binding motif called a PIP box. Upon binding of the PIP box to PCNA on chromatin, CRL4(Cdt2) is recruited and the substrate is ubiquitylated. Importantly, a PIP box cannot be sufficient for destruction, as most PIP box proteins are stable. Using Xenopus egg extracts, we identify two sequence elements in CRL4(Cdt2) substrates that promote their proteolysis: a specialized PIP box that confers exceptionally efficient PCNA binding and a basic amino acid 4 residues downstream of the PIP box, which recruits CRL4(Cdt2) to the substrate-PCNA complex. We also identify two mechanisms that couple CRL4(Cdt2)-dependent proteolysis to the chromatin-bound form of PCNA, ensuring that this proteolysis pathway is active only in S phase or after DNA damage. Thus, CRL4(Cdt2) recognizes an unusual degron, which is assembled specifically on chromatin via the binding of a specialized PIP box to PCNA.