The replication of viruses depends on the cell cycle status of the infected cells. Viruses have evolved functions that alleviate restrictions imposed on their replication by the host. Vpr, an accessory factor of primate lentiviruses, arrests cells at the DNA damage checkpoint in G2 phase of the cell cycle, but the mechanism underlying this effect has remained elusive. Here we report that Vpr proteins of both the human (HIV-1) and the distantly related simian (SIVmac) immunodeficiency viruses specifically associate with a protein complex comprising subunits of E3 ubiquitin ligase assembled on Cullin-4 scaffold (Cul4-DDB1[VprBP]). We show that Vpr binding to Cul4-DDB1[VprBP] leads to increased neddylation and elevated intrinsic ubiquitin ligase activity of this E3. This effect is mediated through the VprBP subunit of the complex, which recently has been suggested to function as a substrate receptor for Cul4. We also demonstrate that VprBP regulates G1 phase and is essential for the completion of DNA replication in S phase. Furthermore, the ability of Vpr to arrest cells in G2 phase correlates with its ability to interact with Cul4-DDB1[VprBP] E3 complex. Our studies identify the Cul4-DDB1[VprBP] E3 ubiquitin ligase complex as the downstream effector of lentiviral Vpr for the induction of cell cycle arrest in G2 phase and suggest that Vpr may use this complex to perturb other aspects of the cell cycle and DNA metabolism in infected cells.