Highly mobile species in the marine environment may be expected to show little differentiation at the population level, but this is often not the case. Instead cryptic population structure is common, and effective conservation will require an understanding of how these patterns evolve. Here we present an assessment from both sides of the North Atlantic of differentiation among populations of a dolphin species that inhabits mainly pelagic waters, the Atlantic white-sided dolphin. We compare eleven putative populations in the western and eastern North Atlantic at mtDNA and microsatellite DNA loci and find reduced nucleotide diversity and signals for historical bottlenecks and post-bottleneck expansions in all regions. We calculate expansion times to have occurred during the early Holocene, following the last glacial maximum (LGM). We find evidence for connectivity among populations from either side of the North Atlantic, and differentiation between putative populations in the far northeast compared with all other areas sampled. Some data suggest the possibility of separate refugia during the LGM explaining this pattern, although ongoing ecological processes may also be a factor. We discuss the implications for developing effective programs of conservation and management in the context of ongoing anthropogenic impact.