The population structure of black-browed (Thalassarche melanophris and T. impavida) and grey-headed (T. chrysostoma) albatrosses was examined using both mitochondrial DNA (mtDNA) and microsatellite analyses. mtDNA sequences from 73 black-browed and 50 grey-headed albatrosses were obtained from five island groups in the Southern Ocean. High levels of sequence divergence were found in both taxa (0.55–7.20% in black-browed albatrosses and 2.10–3.90% in grey-headed albatrosses). Black-browed albatrosses form three distinct groups: Falklands, Diego Ramirez/South Georgia/Kerguelen, and Campbell Island (T. impavida). T. melanophris from Campbell Island contain birds from each of the three groups, indicating high levels of mixture and hybridization. In contrast, grey-headed albatrosses form one globally panmictic population. Microsatellite analyses on a larger number of samples using seven highly variable markers found similar population structure to the mtDNA analyses in both black-browed and grey-headed albatrosses. Differences in population structure between these two very similar and closely related species could be the result of differences in foraging and dispersal patterns. Breeding black-browed albatrosses forage mainly over continental shelves and migrate to similar areas when not breeding. Grey-headed albatrosses forage mainly at frontal systems, travelling widely across oceanic habitats outside the breeding season. Genetic analyses support the current classification of T. impavida as being distinct from T. melanophris, but would also suggest splitting T. melanophris into two groups: Falkland Islands, and Diego Ramirez/South Georgia/Kerguelen.