The two species of Atlantic sea sturgeon on either shore of the North Atlantic, Acipenser sturio in Europe and A. oxyrinchus in North America, probably diverged with the closure of the Tethys Sea and the onset of the North Atlantic Gyre 15-20 million years ago, and contact between them was then presumably precluded by geographic distance. Here we present genetic, morphological and archaeological evidence indicating that the North American sturgeon colonized the Baltic during the Middle Ages and replaced the native sturgeon there, before recently becoming extinct itself in Europe as a result of human activities. In addition to representing a unique transatlantic colonization event by a fish that swims upriver to spawn, our findings have important implications for projects aimed at restocking Baltic waters with the European sturgeon.