Anatomically modern humans reached East Asia more than 40,000 years ago. However, key questions still remain unanswered with regard to the route(s) and the number of wave(s) in the dispersal into East Eurasia. Ancient genomes at the edge of the region may elucidate a more detailed picture of the peopling of East Eurasia. Here, we analyze the whole-genome sequence of a 2,500-year-old individual (IK002) from the main-island of Japan that is  characterized with a typical Jomon culture. The phylogenetic analyses support multiple waves of migration, with IK002 forming a basal lineage to the East and Northeast Asian genomes examined, likely representing some of the earliest-wave migrants who went north from Southeast Asia to East Asia. Furthermore, IK002 shows strong genetic affinity with the indigenous Taiwan aborigines, which may support a coastal route of the Jomon-ancestry migration. This study highlights the power of ancient genomics to provide new insights into the complex history of human migration into East Eurasia.