Dispersal via pelagic larval stages plays a key role in population connectivity of many marine species. The degree of connectivity is often correlated with the time that larvae spend in the water column. The Antarctic notothenioid fishes develop through an unusually long pelagic larval phase often exceeding 1 year. Notothenioids thus represent a prime model system for studying the influence of prolonged larval phases on population structure in otherwise demersal species. Here, we compare the population genetic structure and demographic history of two sub-Antarctic crocodile icefish species (Chaenocephalus aceratus and Champsocephalus gunnari) from the Scotia Arc and Bouvet Island in the Atlantic sector of the Southern Ocean to delineate the relative importance of species-specific, oceanographic and paleoclimatic factors to gene flow. Based on 7 (C. aceratus) and 8 (C. gunnari) microsatellites, as well as two mitochondrial DNA markers (cytochrome b, D-loop), we detect pronounced population genetic structure in both species (amova FSTs range from 0.04 to 0.53). High genetic similarities were found concordantly in the populations sampled at the Southern Scotia Arc between Elephant Island and South Orkney Islands, whereas the populations from Bouvet Island, which is located far to the east of the Scotia Arc, are substantially differentiated from those of the Scotia Arc region. Nonetheless, haplotype genealogies and Bayesian cluster analyses suggest occasional gene flow over thousands of kilometres. Higher divergences between populations of C. gunnari as compared to C. aceratus are probably caused by lower dispersal capabilities and demographic effects. Bayesian skyline plots reveal population size reductions during past glacial events in both species with an estimated onset of population expansions about 25 000 years ago.