It is unclear how historical adaptation versus maladaptation in a prior environment affects population evolvability in a novel habitat. Prior work showed that vesicular stomatitis virus (VSV) populations evolved at constant 37°C improved in cellular infection at both 29°C and 37°C; in contrast, those evolved under random changing temperatures between 29°C and 37°C failed to improve. Here, we tested whether prior evolution affected the rate of adaptation at the thermal-niche edge: 40°C. After 40 virus generations in the new environment, we observed that populations historically evolved at random temperatures showed greater adaptability. Deep sequencing revealed that most of the newly evolved mutations were de novo. Also, two novel evolved mutations in the VSV glycoprotein and replicase genes tended to co-occur in the populations previously evolved at constant 37°C, whereas this parallelism was not seen in populations with prior random temperature evolution. These results suggest that prior adaptation under constant versus random temperatures constrained the mutation landscape that could improve fitness in the novel 40°C environment, perhaps owing to differing epistatic effects of new mutations entering genetic architectures that earlier diverged. We concluded that RNA viruses maladapted to their previous environment could “leapfrog” over counterparts of higher fitness, to achieve faster adaptability in a novel environment.