Climate change, fisheries' pressure on penguin prey, and direct human disturbance of wildlife have all been implicated in causing large shifts in the abundance and distribution of penguins in the Southern Ocean. Without mark-recapture studies, understanding how colonies form and, by extension, how ranges shift is challenging. Genetic studies, particularly focused on newly established colonies, provide a snapshot of colonization and can reveal the extent to which shifts in abundance and occupancy result from changes in demographic rates (e.g., reproduction and survival) or migration among suitable patches of habitat. Here, we describe the population structure of a colonial seabird breeding across a large latitudinal range in the Southern Ocean. Using multilocus microsatellite genotype data from 510 Gentoo penguin (Pygoscelis papua) individuals from 14 colonies along the Scotia Arc and Antarctic Peninsula, together with mitochondrial DNA data, we find strong genetic differentiation between colonies north and south of the Polar Front, that coincides geographically with the taxonomic boundary separating the subspecies P. p. papua and P. p. ellsworthii. Using a discrete Bayesian phylogeographic approach, we show that southern Gentoos expanded from a possible glacial refuge in the center of their current range, colonizing regions to the north and south through rare, long-distance dispersal. Our findings show that this dispersal is important for new colony foundation and range expansion in a seabird species that ordinarily exhibits high levels of natal philopatry, though persistent oceanographic features serve as barriers to movement.