Numerous species of marine megafauna are at risk of extinction and understanding their genetic population structure and demographic history is essential for their conservation. We used mitochondrial DNA and 18 nuclear microsatellite loci, on the largest genetic dataset compiled to date on Australian humpback dolphins (eight sampling sites, 159 samples), to assess their genetic diversity, gene flow and past demographic history along the east coast of Queensland, Australia. Levels of genetic diversity were low (mtDNA: h = 0–0.52, π = 0–0.007; nDNA: Ho = 0.27–0.41; AR = 1.7–2.4). Both mitochondrial (ΦST = 0.49, P = 0.001) and nuclear markers (FST = 0.14, P = 0.001) showed strong genetic structure among sampling sites. Four putative populations were identified, with little contemporary gene flow (m = 0.017 to 0.047) among populations. Genetic divergence follows an isolation-by-distance model (r = 0.38, P = 0.0001), with an apparent restriction in gene flow occurring at scales of 382–509 km. Estimates of contemporary effective population size were low (Ne = 11.5–31.2), with signatures of genetic bottlenecks for all putative populations about 50–150 generations ago. The current low levels of genetic diversity, gene flow, and effective population size in Australian humpback dolphins indicate the effects of historical population bottlenecks and/or founder events during the late Holocene period (~1250–3750 years ago); probably associated with sea level fall and increased intensity of El Niño Southern Oscillation-climatic events. Our results raise important conservation concerns and emphasize the vulnerability of Australian humpback dolphins to stochastic demographic, genetic and environmental processes. Conservation strategies should focus on promoting connectivity among local populations and reducing direct causes of human-related mortality.