G1 cyclins, in association with a cyclin-dependent kinase (CDK), are universal activators of the transcriptional G1-S machinery during entry into the cell cycle. Regulation of cyclin degradation is crucial for coordinating progression through the cell cycle, but the mechanisms that modulate cyclin stability to control cell cycle entry are still unknown. Here, we show that a lack of phosphate downregulates Cln3 cyclin and leads to G1 arrest in Saccharomyces cerevisiae. The stability of Cln3 protein is diminished in strains with low activity of Pho85, a phosphate-sensing CDK. Cln3 is an in vitro substrate of Pho85, and both proteins interact in vivo. More interestingly, cells that carry a CLN3 allele encoding aspartic acid substitutions at the sites of Pho85 phosphorylation maintain high levels of Cln3 independently of Pho85 activity. Moreover, these cells do not properly arrest in G1 in the absence of phosphate and they die prematurely. Finally, the activity of Pho85 is essential for accumulating Cln3 and for reentering the cell cycle after phosphate refeeding. Taken together, our data indicate that Cln3 is a molecular target of the Pho85 kinase that is required to modulate cell cycle entry in response to environmental changes in nutrient availability.