The budding yeast cell cycle oscillates between states of low and high cyclin B/cyclin-dependent kinase (CLB/CDK) activity. Remarkably, the two transitions that link these states are governed by ubiquitin-mediated proteolysis. The transition from low to high CLB activity is triggered by degradation of the CLB/CDK inhibitor SIC1, and the complementary excursion is propelled by the proteolytic destruction of CLBs. The extracellular environment controls this two-state circuit by regulating G1 cyclin/CDK activity, which is directly required for SIC1 proteolysis. Thus, stable oscillations of chromosome replication and segregation in budding yeast are propagated by the interplay between protein phosphorylation and protein degradation.