Understanding observed patterns of connectivity requires an understanding of the evolutionary processes that determine genetic structure among populations, with the most common models being associated with isolation by distance, allopatry or vicariance. Pinnipeds are annual breeders with the capacity for extensive range overlap during seasonal migrations, establishing the potential for the evolution of isolation by distance. Here we assess the pattern of differentiation among six breeding colonies of the southern elephant seal, Mirounga leonina, based on mtDNA and 15 neutral microsatellite DNA markers, and consider measures of their demography and connectivity. We show that all breeding colonies are genetically divergent and that connectivity in this highly mobile pinniped is not strongly associated with geographic distance, but more likely linked to Holocene climate change and demographic processes. Estimates of divergence times between populations were all after the Last Glacial Maximum, and there was evidence for directional migration in a clockwise pattern (with the prevailing current) around the Antarctic. We discuss the mechanisms by which climate change may have contributed to the contemporary genetic structure of southern elephant seal populations and the broader implications.