Species assigned to the anopsobiine centipede genera Anopsobius Silvestri, 1899, and Dichelobius Attems, 1911, are widely distributed on fragments of the Gondwanan supercontinent, including temperate and tropical Australia, New Zealand, New Caledonia, the Cape region of South Africa, and southern South America. Phylogenetic relationships between Australasian and other Gondwanan Anopsobiinae are inferred based on parsimony and maximum likelihood analyses (via direct optimisation) of sequence data for five markers: nuclear ribosomal 18S rRNA and 28S rRNA, mitochondrial ribosomal 12S rRNA and 16S RNA, and the mitochondrial protein-coding cytochrome c oxidase subunit I. New molecular data are added for Anopsobius from South Africa and New Zealand, Dichelobius from New Caledonia, and a new species from Queensland, Australia, Dichelobius etnaensis , sp. nov. The new species is based on distinctive morphological and molecular data. The molecular phylogenies indicate that antennal segmentation in the Anopsobiinae is a more reliable taxonomic character than is spiracle distribution. The former character divides the Gondwanan clade into a 17-segmented group ( Dichelobius ) and a 15-segmented group ( Anopsobius ). Confinement of the spiracles to segments 3, 10 and 12 has at least two origins in the Gondwanan clade. The area cladogram for Dichelobius (Queensland (Western Australia + New Caledonia)) suggests a relictual distribution pruned by extinction.