We used a comparative approach to assess congruence of phylogeographic and genetic structure and diversity, demographic signals, and ratios of pollen to seed dispersal, in the context of species-specific life-history traits, for two widespread sympatric perennial plant species. We sampled Grevillea paradoxa and Melaleuca nematophylla across the species’ ranges throughout the Transitional Rainfall Zone and extending slightly into the Arid Zone of south-west Western Australia. Both species exhibited range-wide phylogeographic and contemporary genetic structure. Moderate haplotype diversity centred in populations on Banded Ironstone Formation (BIF) outcrops and within the Murchison River gorge supports a hypothesis of historical persistence and evolution in these mesic refugia. These features are likely to play important roles in evolutionary persistence with ongoing climate change. There was little evidence of particularly complex demographic histories for the region. More limited haplotype diversity, as well as more limited nuclear genetic diversity and connectivity, in G. paradoxa was consistent with predictions from life-history traits of shorter lifespan, lower fecundity, more limited seed dispersal, and shorter plants, but inconsistent with a prediction of greater pollen dispersal by bird pollinators. Low pollen to seed dispersal ratios suggest seed dispersal plays a greater than expected role in maintaining connectivity in this semi-arid landscape. The study highlights a need for research that integrates aspects of seed ecology and seed and pollen dispersal as well as phylogeographic and genetic patterns in Gondwanan shrublands and other semi-arid landscapes globally.