Populations of anadromous sea lamprey (Petromyzon marinus) have been found to be largely genetically homogeneous across western Europe, and across the eastern seaboard of North America. However, comparatively little is known of the relationship between the European and North American populations. We quantified the extent of population structuring present over a transatlantic scale using mitochondrial DNA sequences. We found clear segregation of the populations on either side of the Atlantic, and considerable genetic homogeneity within Europe over a spatial scale of over 2000 km. The North American populations contained larger genetic diversity than those from Europe, and coalescent analyses showed a corresponding greater overall effective population size. Employing calibration points based on a dated phylogeny of the Petromyzontiformes, our analyses indicated that the North American population has been increasing in effective size since establishment, similar to 500 000 years ago, while the total European population has only undergone population expansion only within the last 125 000 years. This evidence is consistent with a colonisation of Europe from an older North American population, and with the European population persisting through the last glaciation within regional refugia.