During the Last Glacial Maximum (LGM), global sea levels were 120-130 m lower than today, resulting in the emergence of most continental shelves and extirpation of subtidal organisms from these areas. During the interglacial periods, rapid inundation of shelf regions created a dynamic environment for coastal organisms, such as the charismatic leafy seadragon (Phycodurus eques, Syngnathidae), a brooder with low dispersal ability inhabiting kelp beds in temperate Australia. Reconstructions of the paleoshoreline revealed that the increase of shallow areas since the LGM was not uniform across the species’ range and we investigated the effects of these asymmetries on genetic diversity and structuring. Using targeted capture of 857 variable Ultraconserved Elements (UCEs, 2845 SNPs) in 68 individuals, we found that the regionally different shelf topographies were paralleled by contrasting population genetic patterns. In the west, populations may not have persisted through sea-level lows because shallow seabed was very limited. Shallow genetic structure, weak expansion signals and a westward cline in genetic diversity indicates a postglacial recolonization of the western part of the range from a more eastern location following sea-level rise. In the east, shallow seabed persisted during the LGM and increased considerably after the flooding of large bays, which resulted in strong demographic expansions, deeper genetic structure and higher genetic diversity. This study suggests that postglacial flooding with rising sea levels produced locally variable signatures in colonizing populations.