Cellular regulation is believed to evolve in response to environmental variability. However, this has been difficult to test directly. Here, we show that a gene regulation system evolves to the optimal regulatory response when challenged with variable environments. We engineered a genetic module subject to regulation by the lac repressor (LacI) in E. coli, whose expression is beneficial in one environmental condition and detrimental in another. Measured tradeoffs in fitness between environments predict the competition between regulatory phenotypes. We show that regulatory evolution in adverse environments is delayed at specific boundaries in the phenotype space of the regulatory LacI protein. Once this constraint is relieved by mutation, adaptation proceeds toward the optimum, yielding LacI with an altered allosteric mechanism that enables an opposite response to its regulatory ligand IPTG. Our results indicate that regulatory evolution can be understood in terms of tradeoff optimization theory.