In normal and transformed cells, the F-box protein p45(SKP2) is required for S phase and forms stable complexes with p19(SKP1) and cyclin A-cyclin-dependent kinase (CDK)2. Here we identify human CUL-1, a member of the cullin family, and the ubiquitin-conjugating enzyme CDC34 as additional partners of p45(SKP2) in vivo. CUL-1 also associates with cyclin A and p19(SKP1) in vivo and, with p45(SKP2), they assemble into a large multiprotein complex. In Saccharomyces cerevisiae, a complex of similar molecular composition (an F-box protein, a member of the cullin family and a homolog of p19(SKP1)) forms a functional E3 ubiquitin protein ligase complex, designated SCFCDC4, that facilitates ubiquitination of a CDK inhibitor by CDC34. The data presented here imply that the p45(SKP2)-CUL-1-p19(SKP1) complex may be a human representative of an SCF-type E3 ubiquitin protein ligase. We propose that all eukaryotic cells may use a common ubiquitin conjugation apparatus to promote S phase. Finally, we show that multiprotein complex formation involving p45(SKP2)-CUL-1 and p19(SKP1) is governed, in part, by periodic, S phase-specific accumulation of the p45(SKP2) subunit and by the p45(SKP2)-bound cyclin A-CDK2. The dependency of p45(SKP2)-p19(SKP1) complex formation on cyclin A-CDK2 may ensure tight coordination of the activities of the cell cycle clock with those of a potential ubiquitin conjugation pathway.