Rapid freeze-thaw is an extreme mechano-chemical perturbation that results in very low survival of many organisms (as low as a fraction of a percent). Here, using experimental evolution, we show that the budding yeast, Saccharomyces cerevisiae can adapt to freeze-thaw stress in a stereotyped manner, with survival increasing nearly two orders of magnitude from ~2% to ~70% in about 25 cycles of stress exposure. Adapted cells exhibit reduced membrane damage, smaller sizes, higher mass densities, and a lower prevalence of budding. Rheological measurements show that the adapted cells are stiffer and exhibit lower particle mobilities within the cytoplasm. Whole genome sequencing indicates that increased survival is not accompanied by specific (unique) genetic changes, but rather is associated with multiple, distinct genotypes. Concomitant with mechanical changes in the adapted cells, the basal intracellular level of trehalose, a sugar speculated to play a physical role in maintaining membrane and cytoplasmic integrity, exhibits a three-fold increase. Together, these cellular attributes strongly correlate with the entry of cells into a quiescence-like state. A quantitative model that incorporates selection based on cellular quiescence recapitulates the adaptation dynamics, i.e. increase in survival and trehalose levels, seen in experiments. Finally, we find that the evolved mechano-chemical phenotypes are similar even when we use qualitatively different freeze-thaw selection protocols for the evolution, hinting at a convergent adaptation.