Understanding the dynamics of molecular adaptation is a fundamental goal of evolutionary biology. While adaptation to constant environments has been well characterized, the effects of environmental complexity remain seldom studied. One simple but understudied factor is the rate of environmental change. Here we used experimental evolution with RNA viruses to investigate whether evolutionary dynamics varied based on the rate of environmental turnover. We used whole-genome next-generation sequencing to characterize evolutionary dynamics in virus populations adapting to a sudden versus gradual shift onto a novel host cell type. In support of theoretical models, we found that when populations evolved in response to a sudden environmental change, mutations of large beneficial effect tended to fix early, followed by mutations of smaller beneficial effect; as predicted, this pattern broke down in response to a gradual environmental change. Early mutational steps were highly parallel across replicate populations in both treatments. The fixation of single mutations was less common than sweeps of associated “cohorts” of mutations, and this pattern intensified when the environment changed gradually. Additionally, clonal interference appeared stronger in response to a gradual change. Our results suggest that the rate of environmental change is an important determinant of evolutionary dynamics in asexual populations.