Organisms can protect themselves against future environmental change. An example is cross-protection, where physiological adaptation against a present environmental stressor can protect an organism against a future stressor. Another is anticipation, where an organism uses information about its present environment to trigger gene expression and other physiological changes adaptive in future environments. “Predictive” abilities like this exist in organisms that have been exposed to periodic changes in environments. It is unknown how readily they can evolve. To answer this question, we carried out laboratory evolution experiments in the yeast Saccharomyces cerevisiae. Specifically, we exposed three replicate populations of yeast to environments that varied cyclically between two stressors, salt stress and oxidative stress, every 10 generations, for a total of 300 generations. We evolved six replicate control populations in only one of these stressors for the same amount of time. We analyzed fitness changes and genome-scale expression changes in all these evolved populations. Our populations evolved asymmetric cross protection, where oxidative stress protects against salt stress but not vice versa. Gene expression data also suggest the evolution of anticipation and basal gene expression changes that occur uniquely in cyclic environments. Our study shows that highly complex physiological states that are adaptive in future environments can evolve on very short evolutionary time scales.