The large tegument proteins of herpesviruses encode conserved cysteine proteases of unknown function. Here we show that BPLF1, the Epstein-Barr-virus-encoded member of this protease family, is a deneddylase that regulates virus production by modulating the activity of cullin-RING ligases (CRLs). BPLF1 hydrolyses NEDD8 conjugates in vitro, acts as a deneddylase in vivo, binds to cullins and stabilizes CRL substrates. Expression of BPLF1 alone or in the context of the productive virus cycle induces accumulation of the licensing factor CDT1 and deregulates S-phase DNA synthesis. Inhibition of BPLF1 during the productive virus cycle prevents cellular DNA re-replication and inhibits virus replication. Viral DNA synthesis is restored by overexpression of CDT1. Homologues encoded by other herpesviruses share the deneddylase activity. Thus, these enzymes are likely to have a key function in the virus life cycle by inducing a replication-permissive S-phase-like cellular environment.