The collection of several paradoxosomatid species in the context of ecological studies prompted an investigation into the morphology and species-level characteristics of Australian millipedes in the tribe Australiosomatini Brölemann, 1916 (Polydesmida : Paradoxosomatidae). Three new species are described: Akamptogonus caragoon, sp. nov., Australiosoma fulbrighti, sp. nov. and Australiosoma combei, sp. nov. Notes or re-descriptions are provided for nine additional species belonging to the tribe. Scanning electron microscopy was utilised to examine details of the antennal sensory fields, the fifth sternite lamella and associated pores. The presence of the fifth sternite lamella in adult males is considered a synapomorphy for the family Paradoxosomatidae, whereas the prominent tubercle on the first femur in males (adenostyle) represents a synapomorphy of the subfamily Australiosomatinae. With the description of two new species in the genus Australiosoma Brölemann, 1913 a revision of the genus was undertaken with the purpose of constructing a species-level phylogeny. The most commonly described and utilised species-specific characteristics were scored in a data matrix and analysed using PAUP. The analysis resulted in a single, fully resolved tree of the following structure: Hoplatria clavigera ((A. clavigerum, A. inusitatum) (((A. rainbowi, A. nodulosum) A. michelseni) (A. laminatum (A. combei, A. fulbrighti))).