Understanding the molecular basis and dynamics of adaptive evolution of gene expression is a central problem in evolutionary biology. Typically, retrospective analyses are employed to infer adaptive changes in gene expression. To study the dynamics and outcome of gene expression evolution under conditions of strong selection, we performed experimental evolution of yeast cells growing in nitrogen-limited chemostats. Following several hundred generations we found significant divergence of nitrogen-responsive gene expression in lineages with increased fitness. Using high throughput sequencing we identified repeated selection of non-synonymous mutations in the zinc finger DNA binding domain of the GATA transcription factor, GAT1, an activator of the nitrogen catabolite repression (NCR) regulon. We investigated the functional effect of adaptive mutations using a combination of biochemical assays, protein binding microarrays, transcriptional reporters and mathematical modeling. We find that the functional effects of GAT1 mutations are exerted both directly, and indirectly by rewiring incoherent feed-forward loops comprising different GATA transcription factors. Using targeted ultra-deep sequencing we find that evolving populations contain multiple GAT1 mutations at low frequencies (10-2 -10-3) during the initial stages of selection that fail to subsequently increase to appreciable frequencies due to clonal interference. Our study demonstrates that under strong selection the evolution of gene expression is highly repeatable and that adaptive changes in gene expression can result from both direct and indirect effects within the context of a gene regulatory network.