NEDD8/Rub1 is a ubiquitin (Ub)-like post-translational modifier that is covalently linked to cullin (Cul)-family proteins in a manner analogous to ubiquitylation. NEDD8 is known to enhance the ubiquitylating activity of the SCF complex (composed of Skp1, Cul-1, ROC1 and F-box protein), but the mechanistic role is largely unknown. Using an in vitro reconstituted system, we report here that NEDD8 modification of Cul-1 enhances recruitment of Ub-conjugating enzyme Ubc4 (E2) to the SCF complex (E3). This recruitment requires thioester linkage of Ub to Ubc4. Our findings indicate that the NEDD8-modifying system accelerates the formation of the E2-E3 complex, which stimulates protein polyubiquitylation.