Degradation of the mammalian cyclin-dependent kinase (CDK) inhibitor p27 is required for the cellular transition from quiescence to the proliferative state. The ubiquitination and subsequent degradation of p27 depend on its phosphorylation by cyclin–CDK complexes. However, the ubiquitin–protein ligase necessary for p27 ubiquitination has not been identified. Here we show that the F-box protein SKP2 specifically recognizes p27 in a phosphorylation-dependent manner that is characteristic of an F-box-protein–substrate interaction. Furthermore, both in vivo and in vitro, SKP2 is a rate-limiting component of the machinery that ubiquitinates and degrades phosphorylated p27. Thus, p27 degradation is subject to dual control by the accumulation of both SKP2 and cyclins following mitogenic stimulation.