It is a major question in archaeology and anthropology whether human populations started to grow primarily after the advent of agriculture, i.e., the Neolithic time, especially in East Asia, which was one of the centers of ancient agricultural civilization. To answer this question requires an accurate estimation of the time of lineage expansion as well as that of population expansion in a population sample without ascertainment bias. In this study, we analyzed all available mtDNA genomes of East Asians ascertained by random sampling, a total of 367 complete mtDNA sequences generated by the 1000 Genome Project, including 249 Chinese (CHB, CHD, and CHS) and 118 Japanese (JPT). We found that major mtDNA lineages underwent expansions, all of which, except for two JPT-specific lineages, including D4, D4b2b, D4a, D4j, D5a2a, A, N9a, F1a1'4, F2, B4, B4a, G2a1 and M7b1'2'4, occurred before 10 kya, i.e., before the Neolithic time (symbolized by Dadiwan Culture at 7.9 kya) in East Asia. Consistent to this observation, the further analysis showed that the population expansion in East Asia started at 13 kya and lasted until 4 kya. The results suggest that the population growth in East Asia constituted a need for the introduction of agriculture and might be one of the driving forces that led to the further development of agriculture.