Understanding the rate and extent to which populations can adapt to novel environments at their ecological margins is fundamental to predicting the persistence of biological communities during ongoing and rapid global change. Recent range expansion in response to climate change in the UK butterfly Aricia agestis is associated with the evolution of novel interactions with a larval food plant, and the loss of its ability to use an ancestral host species. Using ddRAD analysis of 61,210 variable SNPs from 261 females from throughout the UK range of this species, we identify genomic regions at multiple chromosomes that are associated with evolutionary responses, and their association with demographic history and ecological variation. Gene flow appears widespread throughout the range, despite the apparently fragmented nature of the habitats used by this species. Patterns of haplotype variation between selected and neutral genomic regions suggest that evolution associated with climate adaptation is polygenic, resulting from the independent spread of alleles throughout the established range of this species, rather than the colonization of pre-adapted genotypes from coastal populations. These data suggest that rapid responses to climate change do not depend on the availability of pre-adapted genotypes. Instead, the evolution of novel forms of biotic interaction in A. agestis has occurred during range expansion, through the assembly of novel genotypes from alleles from multiple localities.