MtDNA and microsatellite loci were used to investigate the population structure of Patagonian toothfish at two Australian fishing locations (Macquarie Island, five collections; Heard and McDonald Islands (CCAMLR area 58.4.2), four collections) in the Southern Ocean. Additionally, a small sample of toothfish from the Shag Rocks/South Georgia fishing location (CCAMLR area 48.3) was also examined. Striking mtDNA heterogeneity was detected among the three fishing locations; spatial and temporal collections within the same fishing location were not significantly different. There was weak and inconsistent heterogeneity at several microsatellite loci among the ten collections, and no overall differentiation among the three fishing locations. The mtDNA heterogeneity suggests that gene flow between the two Australian fishing locations and more generally among the three locations within the Southern Ocean is restricted.