Pleistocene sea-level fluctuations profoundly changed landmass configurations around northern Australia. The cyclic emergence of the Torres Strait land bridge and concomitant shifts in the distribution of shallow-water marine habitats repeatedly sundered east and west coast populations. These biogeographical perturbations invoke three possible scenarios regarding the directions of interglacial range expansion: west to east, east to west, or bidirectional. We evaluated these scenarios for the olive sea snake, Aipysurus laevis, by exploring its genetic structure around northern Australia based on 354 individuals from 14 locations in three regions (Western Australia, WA; Gulf of Carpentaria, GoC; Great Barrier Reef, GBR). A 726-bp fragment of the mitochondrial DNA ND4 region revealed 41 variable sites and 38 haplotypes, with no shared haplotypes among the three regions. Population genetic structure was strong overall, phiST=0.78, P<0.001, and coalescent analyses revealed no migration between regions. Genetic diversity was low in the GBR and GoC and the genetic signatures of these regions indicated range or population expansions consistent with their recent marine transgressions around 7000 years ago. By contrast, genetic diversity on most WA reefs was higher and there were no signals of recent expansion events on these reefs. Phylogenetic analyses indicated that GBR and GoC haplotypes were derived from WA haplotypes; however, statistical parsimony suggested that recent range expansion in the GBR-GoC probably occurred from east coast populations, possibly in the Coral Sea. Levels of contemporary female-mediated gene flow varied within regions and reflected potential connectivity among populations afforded by the different regional habitat types.