Calcrete aquifers of the Yilgarn area of Western Australia and the Ngalia Basin, Northern Territory, Australia are known to contain a rich invertebrate stygofauna, including the world’s most diverse assemblage of subterranean diving beetles. Here we determine the generic relationships of these subterranean diving beetle species in the tribe Hydroporini and assess their evolutionary origins. Phylogenetic analyses of 1642 base pairs of mitochondrial DNA (mtDNA), comprising segments of CO1, 16S rRNA, tRNA^leu and ND1 genes, revealed that the subterranean species from the arid zone, previously classified under the genus Nirripirti Watts & Humphreys (Hydroporini), are all closely related to the genus Paroster Sharp. We synonymise the stygobitic genus Nirripirti with the genus Paroster. Factors that may have been important for the transitions to stygobitic life such as historical and contemporary species distributions, reproductive ecology and body size are discussed. We show that pre-adaptations such as preference for temporary, but seasonally reliable, water and preference to live among gravel and sand along running water would have favoured transitions from surface to stygobitic life, but that large body size may have restricted the likelihood of successful transitions.