DNA-protein crosslinks (DPCs) are bulky DNA 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 activity is coupled to 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 triggered by single-stranded DNA, a byproduct of DNA replication. In contrast, SPRTN-mediated DPC degradation is independent of DPC polyubiquitylation but requires polymerase extension of a nascent strand to the lesion. Thus, SPRTN and proteasome activities are coupled to DNA replication by distinct mechanisms and together promote replication across immovable protein barriers.