Cells respond to stress by remodeling their transcriptome through transcription and degradation. Xrn1p-dependent degradation in P-bodies is the most prevalent decay pathway, yet, P-bodies may facilitate not only decay, but also act as a storage compartment. However, which and how mRNAs are selected into different degradation pathways and what determines the fate of any given mRNA in P-bodies remain largely unknown. We devised a new method to identify both common and stress-specific mRNA subsets associated with P-bodies. mRNAs targeted for degradation to P-bodies, decayed with different kinetics. Moreover, the localization of a specific set of mRNAs to P-bodies under glucose deprivation was obligatory to prevent decay. Depending on its client mRNA, the RNA-binding protein Puf5p either promoted or inhibited decay. Furthermore, the Puf5p-dependent storage of a subset of mRNAs in P-bodies under glucose starvation may be beneficial with respect to chronological lifespan.