Although differing rates of environmental turnover should be consequential for the dynamics of adaptive change, this idea has been rarely examined outside of theory. In particular, the importance of RNA viruses in disease emergence warrants experiments testing how differing rates of novel host invasion may impact the ability of viruses to adaptively shift onto a novel host. To test whether the rate of environmental turnover influences adaptation, we experimentally evolved 144 Sindbis virus lineages in replicated tissue-culture environments, which transitioned from being dominated by a permissive host cell type to a novel host cell type. The rate at which the novel host ‘invaded’ the environment varied by treatment. The fitness (growth rate) of evolved virus populations was measured on each host type, and molecular substitutions were mapped via whole genome consensus sequencing. Results showed that virus populations more consistently reached high fitness levels on the novel host when the novel host ‘invaded’ the environment more gradually, and gradual invasion resulted in less variable genomic outcomes. Moreover, virus populations that experienced a rapid shift onto the novel host converged upon different genotypes than populations that experienced a gradual shift onto the novel host, suggesting a strong effect of historical contingency.