The yeast Saccharomyces differentiates into filamentous pseudohyphae when exposed to a poor source of nitrogen in a process involving a collection of transcription factors regulated by nutrient signaling pathways. Phd1 is important for this process in that it regulates expression of most other transcription factors involved in differentiation and can induce filamentation on its own when overproduced. In this article, we show that Phd1 is an unstable protein whose degradation is initiated through phosphorylation by Cdk8 of the RNA polymerase II mediator subcomplex. Phd1 is stabilized by cdk8 disruption, and the naturally filamenting Σ1278b strain was found to have a sequence polymorphism that eliminates a Cdk8 phosphorylation site, which both stabilizes the protein and contributes to enhanced differentiation. In nitrogen-starved cells, PHD1 expression is upregulated and the Phd1 protein becomes stabilized, which causes its accumulation during differentiation. PHD1 expression is partially dependent upon Ste12, which was also previously shown to be destabilized by Cdk8-dependent phosphorylations, but to a significantly smaller extent than Phd1. These observations demonstrate the central role that Cdk8 plays in initiation of differentiation. Cdk8 activity is inhibited in cells shifted to limiting nutrient conditions, and we argue that this effect drives the initiation of differentiation through stabilization of multiple transcription factors, including Phd1, that cause activation of genes necessary for filamentous response.