Genetic diversity data, from Y chromosome and mitochondrial DNA as well as recent genome-wide autosomal SNPs, suggested that mainland Southeast Asia was the major geographic source of East Asian populations. However, these studies also detected Central-South Asia- and/or West Eurasia-related genetic components in East Asia, implying either recent population admixture or ancient migrations via the proposed northern route. To trace the time period and geographic source of these Central-South Asia- and West Eurasia-related genetic components, we sampled 3,826 males (116 populations from China and one population from South Korea) and performed high-resolution genotyping according to the well-resolved Y-chromosome phylogeny. Our data, in combination with the published East Asian Y-haplogroup data, show that there are four dominant haplogroups (accounting for 92.87% of the East Asian Y chromosomes), O-M175, D-M174, C-M130 (not including C5-M356) and N-M231, in both southern and northern East Asian populations, which is consistent with the proposed southern route of modern human origin in East Asia. However, there are other haplogroups (6.79% in total) (E-SRY4064, C5-M356, G-M201, H-M69, I-M170, J-P209, L-M20, Q-M242, R-M207 and T-M70) detected primarily in northern East Asian populations, and were identified as Central-South Asian and/or West Eurasian origin based on the phylogeographic analysis. In particular, evidence of geographic distribution and Y-STR diversity indicate that haplogroup Q-M242 (the ancestral haplogroup of the native American-specific haplogroup Q1a3a-M3) and R-M207 probably migrated into East Asia via the northern route. The age estimation of Y-STR variation within haplogroups suggests the existence of post-Glacial (～18 thousand years ago, kya) migrations via the northern route as well as recent (～3 kya) population admixture. We propose that although the Paleolithic migrations via the southern route played a major role in modern human settlement in East Asia, there are ancient contributions, though limited, from western Eurasia which partly explain the genetic divergence between current southern and northern East Asian populations.