Climatic oscillations during the last glacial maximum (LGM) significantly affected the distribution patterns and genetic structure of extant plants. Northeast China (NEC) is a major biodiversity center in East Asia, and the influence of historical climate change on NEC populations is critical for understanding species responses to future climate change. However, only a few phylogeographic studies of cool-temperate deciduous tree species have been conducted in the area, and results are inconsistent for species with different niches or distribution areas. We employed multiple chloroplast and nuclear markers to investigate the genetic structure of two ecologically contrasting species, Betula platyphylla and B. ermanii, in NEC. Rare haplotypes were identified in the chloroplast genome of these species, and both exhibited high levels of nucleotide diversity based on a fragment of the nuclear gene G3PDH and microsatellites. Moreover, significant phylogeographic structure was detected for B. platyphylla, suggesting that these populations had recolonized from independent glacial refuges, whereas no genetic structure was found for B. ermanii.