Korean pine (Pinus koraiensis) and Picea jezoensis are the most important components of cold temperate forests in northeast Asia. The phylogeographical histories of these widespread conifers may reflect the histories of Quaternary vegetation shifts in this region. Hence, range-wide genetic variation of the species was assessed using maternally inherited mitochondrial DNA sequences. The higher mtDNA diversity and evidence from numerous Pleistocene macrofossils of Korean pine in Japan suggest that the Japanese archipelago once served as a refugium to a much larger Korean pine population with a more extensive range. The presence of the single lineage across the Asian continent implies that the present widespread Korean pine populations could have expanded from a single refugium population after the last glacial periods. Picea jezoensis populations in Hokkaido and Honshu were derived from a single lineage that diverged from a continental lineage; macrofossils were obtained from Honshu from the Pliocene to the early Pleistocene; these suggest that the Japanese lineage might have colonized Honshu via the Korean peninsula through land bridge. Then, two varieties may have occurred in Japan. Kamchatka populations belonged to the continental lineage, suggesting that they could be a relic of a once more northerly distribution.