Shifts in species distribution, or ‘range shifts’, are one of the most commonly documented responses to ocean warming, with important consequences for the function and structure of ecosystems, and for socio-economic activities. Understanding the genetic signatures of range shifts can help build our knowledge of the capacity of species to establish and persist in colonised areas. Here, seven microsatellite loci were used to examine the population connectivity, genetic structure and diversity of Octopus tetricus, which has extended its distribution several hundred kilometres polewards associated with the southwards extension of the warm East Australian Current along south-eastern Australia. The historical distribution and the range extension zones had significant genetic differences but levels of genetic diversity were comparable. The population in the range extension zone was sub-structured, contained relatively high levels of self-recruitment and was sourced by migrants from along the entire geographic distribution. Genetic bottlenecks and changes in population size were detected throughout the range extension axis. Persistent gene flow from throughout the historical zone and moderate genetic diversity may buffer the genetic bottlenecks and favour the range extension of O. tetricus. These characteristics may aid adaptation, establishment, and long-term persistence of the population in the range extension zone.