Background The relationships between North Atlantic and North Pacific faunas through times have been controlled by the variation of hydrographic circumstances in the intervening Arctic Ocean and Bering Strait. We address the history of trans-Arctic connections in a clade of amphi-boreal pelagic fishes using genealogical information from mitochondrial DNA sequence data. The Pacific and Atlantic herrings (Clupea pallasii and C. harengus) have basically vicarious distributions in the two oceans since pre-Pleistocene times. However, remote populations of C. pallasii are also present in the border waters of the North-East Atlantic in Europe. These populations show considerable regional and life history differentiation and have been recognized in subspecies classification. The chronology of the inter-oceanic invasions and genetic basis of the phenotypic structuring however remain unclear. Results The Atlantic and Pacific herrings both feature high mtDNA diversities (large long-term population sizes) in their nativ