Poleward range expansions are a widespread response to recent climate change and are crucial for many species’ future persistence. However for many species evolutionary change in traits such as colonisation history and habitat preference may be necessary to track environmental change across a fragmented landscape. Understanding the likelihood and speed of such adaptive change has therefore become an important issue in determining the effect of ongoing climate change on extinction rates. We conducted an AFLP-based genome scan across the recently-expanded UK range of the Brown Argus butterfly, Polyommatus (subgenus Aricia) agestis, and used both outlier-based (DFDIST and BayeScan) and association-based (Isolation-By-Adaptation) statistical approaches to identify signatures of evolutionary change associated with range expansion, and shifts in host plant use. We present evidence for (a) little effect of range expansion on neutral genetic structure and (b) strong signatures of selection at ~5% AFLP loci associated with both the poleward range expansion of P.agestis and differences in habitat use across the long-established and recently-colonised areas. Patterns of allele frequency change at these candidate loci suggest that adaptation to new habitats at the range margin has involved selection on genes already involved in adaptation to these habitats across the long-established part of the range. Our results suggest that evolutionary change is likely to affect species’ responses to climate change and that genetic variation in ecological traits across species’ distributions should be maximised to facilitate range shifts across a fragmented landscape, particularly in species that show strong associations with particular habitats.