DNA-protein crosslinks (DPCs) are bulky lesions that interfere with DNA metabolism and therefore threaten genomic integrity. Recent studies implicate the metalloprotease SPRTN in S phase removal of DPCs, but how SPRTN is targeted to DPCs during DNA replication is unknown. Using Xenopus egg extracts that recapitulate replication-coupled DPC proteolysis, we show that DPCs can be degraded by SPRTN or the proteasome, which act as independent DPC proteases. Proteasome recruitment requires DPC polyubiquitylation, which is partially dependent on the ubiquitin ligase activity of TRAIP. In contrast, SPRTN-mediated DPC degradation does not require DPC polyubiquitylation but instead depends on nascent strand extension to within a few nucleotides of the lesion, implying that polymerase stalling at the DPC activates SPRTN on both leading and lagging strand templates. Our results demonstrate that SPRTN and proteasome activities are coupled to DNA replication by distinct mechanisms that promote replication across immovable protein barriers.