Patterns of (female) mitochondrial DNA diversity were investigated in the blue mussel Mytilus edulis. Mytilus edulis is a ubiquitous member of contemporary North Atlantic hard-substrate communities and well represented in studies of this region. Mytilus edulis was surveyed in North America and Europe, as well as mid-Atlantic sites in Greenland, Iceland, and the Faroe Islands. Mitochondrial DNA sequences revealed considerable population structure but no monophyly of haplotypes between any major regions. Coalescent analyses suggest that migration across the Atlantic Ocean has prominently been from North American source populations and that Greenland was colonized recently and exclusively from North America. In North America, there was support for two regional groups along the North American coastline. Surprisingly, we also found evidence of recombination between some Mytilus edulis and Mytilus galloprovincialis female mtDNA sequences, particularly in northern Europe.