Despite their evolutionary significance, little is known about the adaptation dynamics of genomically rewired cells in evolution. We have confronted yeast cells carrying a rewired regulatory circuit with a severe and unforeseen challenge. The essential HIS3 gene from the histidine biosynthesis pathway was placed under the exclusive regulation of the galactose utilization system. Glucose containing medium strongly represses the GAL genes including HIS3 and these rewired cells are required to operate this essential gene. We show here that although there were no adapted cells prior to the encounter with glucose, a large fraction of cells adapted to grow in this medium and this adaptation was stably inherited. The adaptation relied on individual cells that switched into an adapted state and, thus, the adaptation was due to a response of many individual cells to the change in environment and not due to selection of rare advantageous phenotypes. The adaptation of numerous individual cells by heritable phenotypic switching in response to a challenge extends the common evolutionary framework and attests to the adaptive potential of regulatory circuits.