Ubiquitin-dependent degradation of regulatory proteins controls many cellular processes, including cell cycle progression, morphogenesis, and signal transduction. Skp1p-cullin-F-box protein (SCF) complexes are ubiquitin ligases composed of a core complex including Skp1p, Cdc53p, one of multiple F-box proteins that are thought to provide substrate specificity to the complex, and the ubiquitin-conjugating enzyme, Cdc34p. It is not understood how SCF complexes are regulated and how physiological conditions alter their levels. Here we show that three F-box proteins, Grr1p, Cdc4p, and Met30p, are unstable components of the SCF, and are themselves degraded in a ubiquitin- and proteasome-dependent manner in vivo. Ubiquitination requires all the core components of the SCF and an intact F-box, suggesting that ubiquitination occurs within the SCF complex by an autocatalytic mechanism. Cdc4p and Grr1p are intrinsically unstable, and their steady-state levels did not fluctuate through the cell cycle. Taken together, our results suggest that ubiquitin-dependent degradation of F-box proteins allows rapid switching among multiple SCF complexes, thereby enabling cells to adapt quickly to changing physiological conditions and progression through different phases of the cell cycle.