Morphologically similar cockroaches in the subfamilies Panesthiinae and Geoscapheinae (Blattaria: Blaberidae) display contrasting feeding habits, behaviour and biogeographical distributions. Panesthiinae, found throughout Asia and Australia, all live in and feed on decaying wood that they burrow into. Geoscapheinae are restricted to Australia and construct and live in burrows in the soil, where they feed on dry leaves taken from the surface. A lack of knowledge about phylogenetic relationships among these cockroaches hinders an understanding of the factors that have shaped the evolution of their diverse lifestyles and biogeography. To address this issue, we sequenced three genes from representatives of nine of the 10 genera in the two subfamilies, and performed phylogenetic analyses. The well–supported topology revealed the Panesthiinae to be paraphyletic with respect to the Geoscapheinae. Soil–burrowing cockroaches appear to have evolved from a lineage of wood burrowers that invaded Australia from the north some time after the merging of the Asian and Australian tectonic plates ca. 20 Myr ago. The main factor promoting the evolution of soil burrowing is likely to have been one of the periods of strong aridity that Australia has experienced since the Miocene period.