Background: We have described the diversity of complete mtDNA sequences from 'relic' groups of the Russian Far East, primarily the Nivkhi (who speak a language isolate with no clear relatedness to any others) and Oroki of Sakhalin, as well as the sedentary Koryak from Kamchatka and the Udegey of Primorye. Previous studies have shown that most of their traditional territory was dramatically reshaped by the expansion of Tungusic-speaking groups. Results: Overall, 285 complete mitochondrial sequences were selected for phylogenetic analyses of published, revised and new mitogenomes. To highlight the likely role of Neolithic expansions in shaping the phylogeographical landscape of the Russian Far East, we focus on the major East Eurasian maternal lineages (Y1a, G1b, D4m2, D4e5, M7a2, and N9b) that are restricted to the coastal area. To obtain more insight into autochthonous populations, we removed from the phylogeographic analysis the G2a, G3a2, M8a1, M9a1, and C4b1 lineages, also found within our samples, likely resulting from admixture between the expanding proto-Tungus and the indigenous Paleoasiatic groups with whom they assimilated. Phylogenetic analysis reveals that unlike the relatively diverse lineage spectrum observed in the Amur estuary and northwestern Sakhalin, the present-day subpopulation on the northeastern coast of the island is relatively homogenous: a sole Y1a sublineage, conspicuous for its nodal mutation at m.16189 T > C!, includes different haplotypes. Sharing of the Y1a-m.16189 T > C! sublineages and haplotypes among the Nivkhi, Ulchi and sedentary Koryak is also evident. Aside from Y1a, the entire tree approach expands our understanding of the evolutionary history of haplogroups G1, D4m, N9b, and M7a2. Specifically, we identified the novel haplogroup N9b1 in Primorye, which implies a link between a component of the Udegey ancestry and the Hokkaido Jomon. Conclusions: Through a comprehensive dataset of mitochondrial genomes retained in autochthonous populations along the coast between Primorye and the Bering Strait, we considerably extended the sequence diversity of these populations to provide new features based on the number and timing of founding lineages. We emphasize the value of integrating genealogical information with genetic data for reconstructing the population history of indigenous groups dramatically impacted by twentieth century resettlement and social upheavals.