CRL4(Cdt2) is a cullin-based E3 ubiquitin ligase that promotes the ubiquitin-dependent proteolysis of various substrates implicated in the control of cell cycle and various DNA metabolic processes such as DNA replication and repair. Substrates for CRL4(Cdt2) E3 ubiquitin ligase include the replication licensing factor Cdt1 and the cyclin-dependent kinase (Cdk) inhibitor p21. Inhibition of this E3 ligase leads to serious abnormalities of the cell cycle and cell death. The ubiquitin-conjugating enzyme (UBC) involved in this important pathway, however, remains unknown. By a proteomic analysis of Cdt2-associated proteins and an RNA interference-based screening approach, we show that CRL4(Cdt2) utilizes two different UBCs to target different substrates. UBCH8, a member of the UBE2E family of UBCs, ubiquitylates and promotes the degradation of p21, both during the normal cell cycle and in UV-irradiated cells. Importantly, depletion of UBCH8 by small interfering RNA (siRNA) increases p21 protein level, delays entry into S phase of the cell cycle, and suppresses the DNA damage response after UV irradiation. On the other hand, members of the UBE2G family of UBCs (UBE2G1 and UBE2G2) cooperate with CRL4(Cdt2) to polyubiquitylate and degrade Cdt1 postradiation, an activity that is critical for preventing origin licensing in DNA-damaged cells. Finally, we show that UBCH8, but not UBE2G1 or UBE2G2, is required for CRL4(Cdt2)-mediated ubiquitylation and degradation of the histone H4 lysine 20 monomethyltransferase Set8, a previously identified CRL4(Cdt2) substrate, as well as for CRL4(Cdt2)-dependent monoubiquitylation of PCNA in unstressed cells. These findings identify the UBCs required for the activity of CRL4(Cdt2) on multiple substrates and demonstrate that different UBCs are involved in the selective ubiquitylation of different substrates by the same E3 complex.