The genetic disjunctions and distributions of long-lived species provide valuable signatures of past demographic response to environmental change. Here we use genetic markers to study two Elaeocarpus species from the Australian Wet Tropics to understand changes in palaeodistribution and demography associated with environmental change on either side of the Black Mountain Corridor (BMC). Contrasting the genetic structure of species with different distributions along altitudinal gradients is important to explore some of the environmental drivers of adaptive evolution. Using coalescent-based molecular and environmental niche models, we investigate the demographic history of two long-lived, altitudinally differentiated species that were previously identified as genetically divergent across the BMC. The origin of the genetic disjunction across the BMC is inferred to have occurred during the last glacial cycle in relation to 13 combined molecular histories of both plastid and nuclear loci. Interestingly, whereas midland populations show a dynamic history of expansion and contraction, the highland populations do not. Molecular history and environmental niche models show the populations north of the BMC have remained relatively stable over time in response to environmental change. Populations south of the BMC have been more dynamic in response to environmental change. These differences are likely to highlight the topographical character and environmental heterogeneity of areas separated by the BMC.