To construct an East Asia mitochondrial DNA (mtDNA) phylogeny, we sequenced the complete mitochondrial genomes of 672 Japanese individuals (http://www.giib.or.jp/mtsnp/index_e.html). This allowed us to perform a phylogenetic analysis with a pool of 942 Asiatic sequences. New clades and subclades emerged from the Japanese data. On the basis of this unequivocal phylogeny, we classified 4713 Asian partial mitochondrial sequences, with <10% ambiguity. Applying population and phylogeographic methods, we used these sequences to shed light on the controversial issue of the peopling of Japan. Population-based comparisons confirmed that present-day Japanese have their closest genetic affinity to northern Asian populations, especially to Koreans, which finding is congruent with the proposed Continental gene flow to Japan after the Yayoi period. This phylogeographic approach unraveled a high degree of differentiation in Paleolithic Japanese. Ancient southern and northern migrations were detected based on the existence of basic M and N lineages in Ryukyuans and Ainu. Direct connections with Tibet, parallel to those found for the Y-chromosome, were also apparent. Furthermore, the highest diversity found in Japan for some derived clades suggests that Japan could be included in an area of migratory expansion to Continental Asia. All the theories that have been proposed up to now to explain the peopling of Japan seem insufficient to accommodate fully this complex picture.