The evolution of gene regulatory networks is poorly understood, partly because we lack appropriate model systems that allow the development of quantitative, experimentally testable predictions. To address this problem, we developed quantitative models to predict the evolutionary dynamics of a two-component synthetic gene circuit. Then we inserted the synthetic gene network module into the budding yeast genome and validated the computational predictions by experimental evolution in specific environments that affected the gene network’s costs and benefits to the host. In agreement with computational predictions, we found that mutations: (i) target and eliminate the module if it has only cost; (ii) activate the module if it is potentially beneficial and carries no cost; and (iii) fine-tune the module’s response if it has excessive cost and/or insufficient benefit. These results suggest that gene network evolution may be predictable from the interplay of network dynamics with environment-dependent costs and benefits, all of which can be determined prior to evolution.