Nutrient limitation results in an activation of autophagy in organisms ranging from yeast, nematodes and flies to mammals. Several evolutionary conserved nutrient-sensing kinases are critical for efficient adaptation of yeast cells to glucose, nitrogen or phosphate depletion, subsequent cell-cycle exit and the regulation of autophagy. Here, we demonstrate that phosphate restriction results in a prominent extension of yeast lifespan that requires the coordinated activity of autophagy and the multivesicular body pathway, enabling efficient turnover of cytoplasmic and plasma membrane cargo. While the multivesicular body pathway was essential during the early days of aging, autophagy contributed to long-term survival at later days. The cyclin-dependent kinase Pho85 was critical for phosphate restriction-induced autophagy and full lifespan extension. In contrast, when cell-cycle exit was triggered by exhaustion of glucose instead of phosphate, Pho85 and its cyclin, Pho80, functioned as negative regulators of autophagy and lifespan. The storage of phosphate in form of polyphosphate was completely dispensable to in sustaining viability under phosphate restriction. Collectively, our results identify the multifunctional, nutrient-sensing kinase Pho85 as critical modulator of longevity that differentially coordinates the autophagic response to distinct kinds of starvation.