The Japanese Archipelago is widely covered with acidic soil made of volcanic ash, an environment which is detrimental to the preservation of ancient biomolecules. More than 10,000 Palaeolithic and Neolithic sites have been discovered nationwide, but few skeletal remains exist and preservation of DNA is poor. Despite these challenging circumstances, we succeeded in obtaining a complete mitogenome (mitochondrial genome) sequence from Palaeolithic human remains. We also obtained those of Neolithic (the hunting-gathering Jomon and the farming Yayoi cultures) remains, and over 2,000 present-day Japanese. The Palaeolithic mitogenome sequence was not found to be a direct ancestor of any of Jomon, Yayoi, and present-day Japanese people. However, it was an ancestral type of haplogroup M, a basal group of the haplogroup M. Therefore, our results indicate continuity in the maternal gene pool from the Palaeolithic to present-day Japanese. We also found that a vast increase of population size happened and has continued since the Yayoi period, characterized with paddy rice farming. It means that the cultural transition, i.e. rice agriculture, had significant impact on the demographic history of Japanese population.