To clarify the colonizing process of East/Northeast Asia as well as the peopling of the Americas, identifying the genetic characteristics of Paleolithic Siberians is indispensable. However, no genetic information on the Paleolithic Siberians has hitherto been reported. In the present study, we analyzed ancient DNA recovered from Jomon skeletons excavated from the northernmost island of Japan, Hokkaido, which was connected with southern Siberia in the Paleolithic period. Both the control and coding regions of their mitochondrial DNA (mtDNA) were analyzed in detail, and we confidently assigned 54 mtDNAs to relevant haplogroups. Haplogroups N9b, D4h2, G1b, and M7a were observed in these individuals, with N9b being the predominant one. The fact that all these haplogroups, except M7a, were observed with relatively high frequencies in the southeastern Siberians, but were absent in southeastern Asian populations, implies that most of the Hokkaido Jomon people were direct descendants of Paleolithic Siberians. The coalescence time of N9b (ca. 22,000 years) was before or during the last glacial maximum, implying that the initial trigger for the Jomon migration in Hokkaido was increased glaciations during this period. Interestingly, Hokkaido Jomons lack specific haplogroups that are prevailing in present-day native Siberians, implying that diffusion of these haplogroups in Siberia might have been after the beginning of the Jomon era, about 15,000 years before present.