Populations experiencing similar selection pressures can sometimes diverge in the genetic architectures underlying evolved complex traits. We used RNA virus populations of large size and high mutation rate to study the impact of historical environment on genome evolution, thus increasing our ability to detect repeatable patterns in the evolution of genetic architecture. Experimental vesicular stomatitis virus populations were evolved on HeLa cells, on MDCK cells, or on alternating hosts. Turner and Elena (2000. Cost of host radiation in an RNA virus. Genetics. 156:1465–1470.) previously showed that virus populations evolved in single-host environments achieved high fitness on their selected hosts but failed to increase in fitness relative to their ancestor on the unselected host and that alternating-host–evolved populations had high fitness on both hosts. Here we determined the complete consensus sequence for each evolved population after 95 generations to gauge whether the parallel phenotypic changes were associated with parallel genomic changes. We also analyzed the patterns of allele substitutions to discern whether differences in fitness across hosts arose through true pleiotropy or the presence of not only a mutation that is beneficial in both hosts but also 1 or more mutations at other loci that are costly in the unselected environment (mutation accumulation [MA]). We found that ecological history may influence to what extent pleiotropy and MA contribute to fitness asymmetries across environments. We discuss the degree to which current genetic architecture is expected to constrain future evolution of complex traits, such as host use by RNA viruses.