Environmental cues in an ecological niche are often temporal in nature. For instance, in temperate climates, temperature is higher in daytime compared to during night. In response to these temporal cues, bacteria have been known to exhibit anticipatory regulation, whereby triggering response to a yet to appear cue. Such an anticipatory response in known to enhance Darwinian fitness, and hence, is likely an important feature of regulatory networks in microorganisms. However, the conditions under which an anticipatory response evolves as an adaptive response are not known. In this work, we develop a quantitative model to study response of a population to two temporal environmental cues, and predict variables which are likely important for evolution of anticipatory regulatory response. We follow this with experimental evolution of Escherichia coli in alternating environments of rhamnose and paraquat for ∼850 generations. We demonstrate that growth in this cyclical environment leads to evolution of anticipatory regulation. As a result, pre-exposure to rhamnose leads to a greater fitness in paraquat environment. Genome sequencing reveals that this anticipatory regulation is encoded via mutations in global regulators. Overall, our study contributes to understanding of how environment shapes the topology of regulatory networks in an organism.