The prehistoric peopling of East Asia by modern humans remains controversial with respect to early population migrations. Here, we present a systematic sampling and genetic screening of an East Asian-specific Y-chromosome haplogroup (O3-M122) in 2,332 individuals from diverse East Asian populations. Our results indicate that the O3-M122 lineage is dominant in East Asian populations, with an average frequency of 44.3%. The microsatellite data show that the O3-M122 haplotypes in southern East Asia are more diverse than those in northern East Asia, suggesting a southern origin of the O3-M122 mutation. It was estimated that the early northward migration of the O3-M122 lineages in East Asia occurred approximately 25,000-30,000 years ago, consistent with the fossil records of modern humans in East Asia.