Phylogeographic patterns of trees in topographically subdued, unglaciated landscapes are under-reported, and might reflect population persistence and the influences of environment and distance over historical (~2.6Mya-present) and contemporary (recent generations) time-scales. We examined this hypothesis using genetic analyses of four slowly evolving non-coding chloroplast sequences and 16 nuclear microsatellites in the tree Corymbia calophylla from south-western Australia that has been unglaciated since the Permian (.300-250Mya). We found strong population differentiation for chloroplast DNA and low differentiation for nuclear loci, consistent with higher gene flow by pollen than seed. We identified three divergent chloroplast lineages distributed in central, north and south geographic regions, and diversifying from the early (.3.028Mya), mid- (.0.793Mya) and late- (.0.426Mya) Pleistocene, respectively. Moderate-high nucleotide diversity with population-specific haplotypes supported long-term persistence but diversification of lineages provided evidence of unexpected episodic range expansion. We suggest this pattern reflects environmental influences of climatic oscillations during progressive drying of south-western Australia from the early Pleistocene. Significant tests for isolation by environment for nuclear loci also supported an influence of contemporary environmental (aridity) conditions on genetic structure, but isolation by distance (IBD) was greater. Significant chloroplast and nuclear IBD suggested distance was a major influence on gene flow at both time-scales.