'Living fossils' are testimonies of long-term sustained ecological success, but how demographic history and natural selection contributed to their survival, resilience, and persistence in the face of Quaternary climate fluctuations remains unclear. To better understand the interplay between demographic history and selection in shaping genomic diversity and evolution of such organisms, we assembled the whole genome ofCercidiphyllum japonicum, a widespread East Asian Tertiary relict tree, and resequenced 99 individuals ofC. japonicumand its sister species,Cercidiphyllum magnificum(Central Japan). We dated this speciation event to the mid-Miocene, and the intraspecific lineage divergence ofC. japonicum(China vs Japan) to the Early Pliocene. Throughout climatic upheavals of the late Tertiary/Quaternary, population bottlenecks greatly reduced the genetic diversity ofC. japonicum. However, this polymorphism loss was likely counteracted by, first, long-term balancing selection at multiple chromosomal and heterozygous gene regions, potentially reflecting overdominance, and, second, selective sweeps at stress response and growth-related genes likely involved in local adaptation. Our findings contribute to a better understanding of how living fossils have survived climatic upheaval and maintained an extensive geographic range; that is, both types of selection could be major factors contributing to the species' survival, resilience, and persistence.