Prions are fascinating but often misunderstood protein aggregation phenomena. The traditional association of the mammalian prion protein with disease has overshadowed a potentially more interesting attribute of prions: their ability to create protein-based molecular memories. In fungi, prions alter the relationship between genotype and phenotype in a heritable way that diversifies clonal populations. Recent findings in yeast indicate that prions might be much more common than previously realized. Moreover, prion-driven phenotypic diversity increases under stress, and can be amplified by the dynamic maturation of prion-initiating states. In this article, we suggest that these qualities allow prions to act as 'bet-hedging' devices that facilitate the adaptation of yeasts to stressful environments, and might speed the evolution of new traits.