We determine the phylogenetic backbone of the East Asian mtDNA tree by using published complete mtDNA sequences and assessing both coding and control region variation in 69 Han individuals from southern China. This approach assists in the interpretation of published mtDNA data on East Asians based on either control region sequencing or restriction fragment length polymorphism (RFLP) typing. Our results confirm that the East Asian mtDNA pool is locally region-specific and completely covered by the two superhaplogroups M and N. The phylogenetic partitioning based on complete mtDNA sequences corroborates existing RFLP-based classification of Asian mtDNA types and supports the distinction between northern and southern populations. We describe new haplogroups M7, M8, M9, N9, and R9 and demonstrate by way of example that hierarchically subdividing the major branches of the mtDNA tree aids in recognizing the settlement processes of any particular region in appropriate time scale. This is illustrated by the characteristically southern distribution of haplogroup M7 in East Asia, whereas its daughter-groups, M7a and M7b2, specific for Japanese and Korean populations, testify to a presumably (pre-)Jomon contribution to the modern mtDNA pool of Japan.