Genetically identical cells frequently display substantial heterogeneity in gene expression, cellular morphology and physiology. It has been suggested that by rapidly generating a subpopulation with novel phenotypic traits, phenotypic heterogeneity (or plasticity) accelerates the rate of adaptive evolution in populations facing extreme environmental challenges. This issue is important as cell-to-cell phenotypic heterogeneity may initiate key steps in microbial evolution of drug resistance and cancer progression. Here, we study how stochastic transitions between cellular states influence evolutionary adaptation to a stressful environment in yeast Saccharomyces cerevisiae. We developed inducible synthetic gene circuits that generate varying degrees of expression stochasticity of an antifungal resistance gene. We initiated laboratory evolutionary experiments with genotypes carrying different versions of the genetic circuit by exposing the corresponding populations to gradually increasing antifungal stress. Phenotypic heterogeneity altered the evolutionary dynamics by transforming the adaptive landscape that relates genotype to fitness. Specifically, it enhanced the adaptive value of beneficial mutations through synergism between cell-to-cell variability and genetic variation. Our work demonstrates that phenotypic heterogeneity is an evolving trait when populations face a chronic selection pressure. It shapes evolutionary trajectories at the genomic level and facilitates evolutionary rescue from a deteriorating environmental stress.