Archaeological and ancient DNA studies revealed that Shandong,a multi-culture center in northern coastal China,was home to ancient populations having ancestry related to both northern and southern East Asian populations.However,the limited temporal and geographical range of previous studies have been insufficient to describe the population history of this region in greater detail.Here,we report the analysis of 86 complete mitochondrial genomes from the remains of 9500 to 1800-year-old humans from 12 archaeological sites across Shandong.For samples older than 4600 years before present (BP),we found haplogroups D4,D5,B4c1,and B5b2,which are observed in present-day northern and southern East Asians.For samples younger than 4600 BP,haplogroups C (C7a1 and C7b),M9 (M9a1),and F (F1a1,F2a,and F4a1) begin to appear,indicating changes in the Shandong maternal genetic structure starting from the beginning of the Longshan cultural period.Within Shandong,the genetic exchange is possible between the coastal and inland regions after 3100 BP.We also discovered the BSb2 lineage in Shandong populations,with the oldest Bianbian individual likely related to the ancestors of some East Asians and North Asians.By reconstructing a maternal genetic structure of Shandong populations,we provide greater resolution of the population dynamics of the northern coastal East Asia over the past nine thousand years.