Gene order is often highly conserved within taxonomic groups, such that organisms with rearranged genomes tend to be less fit than wild type gene orders, and suggesting natural selection favors genome architectures that maximize fitness. But it is unclear whether rearranged genomes hinder adaptability: capacity to evolutionarily improve in a new environment. Negative-sense non-segmented RNA viruses (order Mononegavirales) have specific genome architecture: 3’ UTR - core protein genes - envelope protein genes - RNA-dependent RNA-polymerase gene - 5’ UTR. To test how genome architecture affects RNA virus evolution, we examined vesicular stomatitis virus (VSV) variants with the nucleocapsid (N) gene moved sequentially downstream in the genome. Because RNA polymerase stuttering in VSV replication causes greater mRNA production in upstream genes, N gene translocation toward the 5’ end leads to stepwise decreases in N transcription, viral replication and progeny production, and also impacts the activation of type 1 interferon mediated antiviral responses. We evolved VSV gene-order variants in two prostate cancer cell lines: LNCap cells deficient in innate immune response to viral infection, and PC-3 cells that mount an IFN stimulated anti-viral response to infection. We observed that gene order affects phenotypic adaptability (reproductive growth; viral suppression of immune function), especially on PC-3 cells that strongly select against virus infection. Overall, populations derived from the least-fit ancestor (most-altered N position architecture) adapted fastest, consistent with theory predicting populations with low initial fitness should improve faster in evolutionary time. Also, we observed correlated responses to selection, where viruses improved across both hosts, rather than suffer fitness trade-offs on unselected hosts. Whole genomics revealed multiple mutations in evolved variants, some of which were conserved across selective environments for a given gene order.