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 native basins, but an ocean-wide homogeneity of C. harengus is contrasted by deep east-west Pacific subdivision within Pacific C. pallasii. The outpost populations of C. pallasii in NE Europe are identified as members of the western Pacific C. pallasii clade, with some retained inter-oceanic haplotype sharing. They have lost diversity in colonization bottlenecks, but have also thereafter accumulated abundant new variation. The data delineate three phylogeographic groups within the European C. pallasii: herring from the inner White Sea; herring from the Mezen and Chesha Bays; and a strongly bottlenecked peripheral population in Balsfjord of the Norwegian Sea. Conclusions: The NE European outposts of C. pallasii are judged to be early post-glacial colonists from the NW Pacific. A strong regional substructure has evolved since that time, in contrast to the apparent broad-scale uniformity maintained by herrings in their native basins. The structure only partly matches the previous biological concepts based on seasonal breeding stocks or geographical subspecies designations. The trans-Arctic herring phylogeography is notably similar to those of the amphi-boreal mollusk taxa Macoma and Mytilus, suggesting similar histories of inter-oceanic connections. We also considered the time dependency of molecular rates, critical for interpreting timing of relatively recent biogeographical events, by comparing the estimates from coding and non-coding mitochondrial regions of presumably different mutation dynamics.