Many species are shifting their ranges in response to global climate change. Range expansions are known to have profound effects on the genetic composition of populations. The evolution of dispersal during range expansion increases invasion speed, provided that a species can adapt sufficiently fast to novel local conditions. Genetic diversity at the expanding range border is however depleted due to iterated founder effects. The surprising ability of colonizing species to adapt to novel conditions while being subjected to genetic bottlenecks is termed ‘the genetic paradox of invasive species’. Mutational processes have been argued to provide an explanation for this paradox. Mutation rates can evolve, under conditions that favor an increased rate of adaptation, by hitchhiking on beneficial mutations through induced linkage disequilibrium. Here we argue that spatial sorting, iterated founder events, and population structure benefit the build-up and maintenance of such linkage disequilibrium. We investigate if the evolution of mutation rates could play a role in explaining the ‘genetic paradox of invasive species’ for a sexually reproducing species colonizing a landscape of gradually changing conditions.