Environmental changes over the Plio-Pleistocene have been key drivers of speciation patterns and genetic diversification in high-latitude and mesic environments, yet comparatively little is known about the evolutionary history of species in arid environments. We applied phylogenetic and phylogeographic analyses to understand the evolutionary history of Warramaba grasshoppers from the Australian arid zone, a group including sexual and parthenogenetic lineages. Sequence data (mitochondrial COI) showed that the four major sexual lineages within Warramaba most likely diverged in the Pliocene, around 2-7 million years ago. All sexual lineages exhibited considerable phylogenetic structure. Detailed analyses of the hybrid parthenogenetic species W. virgo and its sexual progenitors showed a pattern of high phylogenetic diversity and phylogeographic structure in northern lineages, and low diversity and evidence for recent expansion in southern lineages. Northern sexual lineages persisted in localized refugia over the Pleistocene, with sustained barriers promoting divergence over this period. Southern parts of the present range became periodically unsuitable during the Pleistocene, and it is into this region that parthenogenetic lineages have expanded. Our results strongly parallel those for sexual and parthenogenetic lineages of the gecko Heteronotia from the same region, indicating a highly general effect of Plio-Pleistocene environmental change on diversification processes in arid Australia.