The leafy seadragon (Phycodurus eques, Syngnathidae), is a charismatic endemic of Australia’s temperate coast. The species exhibits remarkable camouflage in its kelp and seagrass habitat. These habitats have been retreating throughout the range of the species, leading to concerns about the persistence of leafy seadragons. Despite being a popular aquarium display and a flagship for coastal conservation, little is known about leafy seadragon biology. We used 7 microsatellite markers and 2 mitochondrial DNA fragments to investigate the population structuring and genetic diversity of 71 individuals. Bayesian cluster analysis identified 2 main genetic partitions, one in Western Australia and the other in South Australia. Shallower, yet significant, differentiation of mitochondrial DNA (φ ST) and microsatellites (F ST, F′ ST, D) was found on the smaller geographic scales in South Australia. Distinct groups were supported in Encounter Bay, on both shores of Gulf St Vincent, and in Spencer Gulf. Sample sizes were too small in the eastern Great Australian Bight and in the westernmost locality to address genetic differentiation in these regions. Overall genetic diversity was moderate to low, but particularly low levels were found in the Western Australian cluster. This latter point needs confirmation at other sites in Western Australia. In South Australia, signatures of demographic changes were detected, which may have been caused by a population expansion due to post-glacial reflooding of the gulfs. The Western Australian and South Australian clusters appeared as demographically independent units. Conservation actions should focus on preserving genetic diversity at local scales and maintaining habitat connectivity.