To thrive in a changing world, evolving populations must be able to generate variants adapted to future environments. In one environmental state, however, there is no direct selection pressure on a population to make adaptive variation more accessible. Whether natural selection can drive evolving organisms to manifest this adaptive variation, and become more evolvable, is widely debated. Using a simple instance of evolution, we show that evolvability is favoured when a population evolves in a changing environment. We also highlight a novel mechanism through which populations evolve to access relatively higher amounts of adaptive variation under these conditions. This mechanism is not sufficiently explained by natural selection but is rather a combination of deterministic selection dynamics and stochastic search of the genotype space during evolution. Thus, we demonstrate that evolvability can and does evolve, and could play an important role in the adaptation of living systems to a changing environment.