Microbes can respond quickly to environmental disturbances through adaptation. However, processes determining the constraints on this adaptation are not well understood. One process that could affect the rate of adaptation to environmental perturbations is genetic robustness, the ability to maintain phenotype despite mutation. Genetic robustness has been theoretically linked to evolvability but rarely tested empirically using evolving populations. We used populations of the RNA bacteriophage Φ6 previously characterized as differing in robustness, and passaged them through a repeated environmental disturbance: periodic 45°C heat shock. The robust populations evolved faster to withstand the disturbance, relative to the less robust (brittle) populations. The robust populations also achieved relatively greater thermotolerance by the end of the experimental evolution. Sequencing revealed that thermotolerance occurred via a key mutation in gene P5 (viral lysis protein), previously shown to be associated with heat shock survival in the virus. Whereas this identical mutation fixed in all of the independently evolving robust populations, it was absent in some brittle populations, which instead fixed a less beneficial mutation. We concluded that robust populations adapted faster to the environmental change, and more easily accessed mutations of large benefit. Our study shows that genetic robustness can play a role in determining the relative ability for microbes to adapt to changing environments.