Amyloids and amyloid-based prions are self-perpetuating protein aggregates which can spread by converting a normal protein of the same sequence into a prion form. They are associated with diseases in humans and mammals, and control heritable traits in yeast and other fungi. Some amyloids are implicated in biologically beneficial processes. As prion formation generates reproducible memory of a conformational change, prions can be considered as molecular memory devices. We have demonstrated that in yeast, stress-inducible cytoskeleton-associated protein Lsb2 forms a metastable prion in response to high temperature. This prion promotes conversion of other proteins into prions and can persist in a fraction of cells for a significant number of cell generations after stress, thus maintaining the memory of stress in a population of surviving cells. Acquisition of an amino acid substitution required for Lsb2 to form a prion coincides with acquisition of increased thermotolerance in the evolution of Saccharomyces yeast. Thus the ability to form an Lsb2 prion in response to stress coincides with yeast adaptation to growth at higher temperatures. These findings intimately connect prion formation to the cellular response to environmental stresses.