The scydmaenine tribe Eutheiini is recorded from Australia for the first time. Paraneseuthia carltoni sp. n. and P. booloumba sp. n. are described and illustrated, both from Queensland. In a parsimony-based phylogenetic analysis using adult morphological characters including genital features, the Australian species together with the Melanesian type species of Paraneseuthia Franz, P. peckorum Franz, were found to be more closely related to East Palearctic congeners than to most of the Paraneseuthia in the Sunda-Papuan area. The topology of the tree and biogeographic data suggest a Sundaland origin of this genus, with three major dispersal routes from a center located in present-day Sumatra: (i) north-eastern colonization of the Palearctic Far East, via a continental or island-arc route; (ii) south-eastern dispersal to East Australia; and (iii) eastern dispersal to Melanesia, possibly via the Quaternary Outer-Melanesian Arc. The important role of dispersal in the evolution of Paraneseuthia is supported by the presence of this genus on isolated volcanic islands, such as the southern Moluccas and Fiji, which were never connected to larger land masses. and Paweł Jałoszyński.