Published phylogenies of two eucalypt clades, red bloodwoods 'Corymbia' subgenus 'Corymbia' and eudesmids 'Eucalyptus' subgenus 'Eudesmia' (Myrtaceae), were combined for an analysis of historical biogeographical area relationships within continental Australia. The method of paralogy-free subtree analysis was used to eliminate geographical paralogy; the paralogy-free subtrees were coded as characters for parsimony analysis to find the minimal and area cladogram, which proved to be informative of a continent-wide pattern. The eucalypt fossil record and molecular dating studies allow an interpretation of the biogeographical history in terms of major vicariance events that date from the early Paleogene. The summary area cladogram shows the wet jarrah forest region of South-West Western Australia, a region of high endemism, as the earliest to differentiate from all other areas, isolated by marine inundation across southern Australia and climatic cooling in the Late Eocene–Early Oligocene. From about this time, regionalization continued, with warmer conditions and monsoonal climate developing in central and northern Australia, and cooling in the south-east. Northern and eastern humid and semi-humid areas were related as a track, but with increased aridity in the interior of the continent, the monsoonal climate contracted northwards. The Australian Monsoon Tropics (AMT: Kimberley, Top End, Arnhem, Cape York and inland north-east Queensland) differentiated from eastern areas (Queensland wet tropics to McPherson–Macleay). Our results also show all arid and semi-arid regions as related, suggestive of a historically cohesive interior biota rather than repeated colonizations of the interior from the periphery of the continent. Climate largely differentiates hot arid areas in the north (Pilbara, Northern and Central deserts) from arid areas in the south (south-west interzone, Wheatbelt, Goldfields and Great Victoria Desert).