Perhaps no other continent has a darker history in terms of the introduction of foreign species than Australia, with the classics – rabbits, pigs, goats, cats, and cane toads – having devastating ecological and economic impacts. However, invasive species also provide an evolutionary experiment that potentially allows us to understand range expansion dynamics, rapid evolutionary change and adaptation to novel environments. The European common starling, Sturnus vulgaris, is a successful invasive bird that has been established in Australia for 40 generations. It is primarily found across the eastern and southern areas of Australia but found within a wide range of environmental conditions. Using Genotyping By Sequencing (GBS), we determined the SNP genotype of 540 common starlings from 24 locations across the starlings’ environmental range in Australia. This allowed the identification of regional patterns of genetic structure and connectivity within a heterogeneous landscape and allowed us to relate environmental and landscape features to genetic patterns. By understanding the response of invasive species to their non-native range we will gain greater insight into the interaction of species and their environment and better understand how invasions may proceed. Such knowledge could help guide the allocation of sparse resources available for managing invasive species.