Early proteomic adaptations in cells serve as an initial line of defense, allowing populations to cope with environmental changes before long-term genetic alterations occur. Therefore, they are important in determining the trajectory taken by populations experiencing stress. Using a representative set of genes and DNA barcoding in , we examine how two facets of these adaptations, gene expression and fitness, are distributed within populations experiencing different types and levels of abiotic stress. Together, our data reveal two fundamentally distinct modes of population-level stress response in yeast. The first mode is complex and exploratory, in which individual members adjust the expression of a large part of their genes, seemingly searching phenotypic space for a solution. This leads to phenotypic and fitness heterogeneity within the population. The second mode is degenerate, with all individuals adopting similar gene-expression levels and obtaining uniform fitness. The first mode is employed when a prevalent stress is encountered, and the second under a rare one. This hints at a role for historical encounters in phenotypic plasticity.