Populations of genetically uniform microorganisms exhibit phenotypic heterogeneity, where individual cells have varying phenotypes. Such phenotypes include fitness-determining traits. Phenotypic heterogeneity has been linked to increased population-level fitness in laboratory studies, but its adaptive significance for wild microorganisms in the natural environment is unknown. Here, we addressed this by testing heterogeneity in yeast isolates from diverse environmental sites, each polluted with a different principal contaminant, as well as from corresponding control locations. We found that cell-to-cell heterogeneity (in resistance to the appropriate principal pollutant) was prevalent in the wild yeast isolates. Moreover, isolates with the highest heterogeneity were consistently observed in the polluted environments, indicating that heterogeneity is positively related to survival in adverse conditions in the wild. This relationship with survival was stronger than for the property of mean resistance (IC50) of an isolate. Therefore, heterogeneity could be the major determinant of microbial survival in adverse conditions. Indeed, growth assays indicated that isolates with high heterogeneities had a significant competitive advantage during stress. Analysis of yeasts after cultivation for ≥ 500 generations additionally showed that high heterogeneity evolved as a heritable trait during stress. The results showed that environmental stress selects for wild microorganisms with high levels of phenotypic heterogeneity.