We present a molecular phylogenetic analysis of 2808 aligned bp of rrnL, cox1, cob, H3 and 18S rRNA of all major morphological groups of Papuadytes diving beetles (Coleoptera: Dytiscidae) which are diverse in running water habitats throughout the Australian region. We focus on the origin of the fauna of the megadiverse islands of New Guinea and New Caledonia. Parsimony as well as Bayesian analyses suggest a basal position of Australian species in a paraphyletic series, with more recent nested radiations in New Caledonia and New Guinea. According to molecular clock analyses, both landmasses were colonized during the Miocene, which matches geological data and corroborates similar findings in other taxonomic groups. Our analyses suggest that dispersal played an important role in the formation of these large insular faunas, although successful colonization appears to be a rare event, and, in this case, is unidirectional. Whether or not a lineage is present on an island is due to chance: Papuadytes are absent from Fiji, where related Copelatus have radiated extensively in the same habitats occupied by Papuadytes in New Caledonia and New Guinea, while Copelatus are absent from New Caledonia. Lineages of Papuadytes apparently colonized New Caledonia twice, around 14 and 9 MYA according to the molecular calibration, and both lineages are derived from an Australian ancestor. The older clade is represented only by two apparently relictual mountain species (one morphologically strongly adapted to highly ephemeral habitats), while the younger clade contains at least 18 species exhibiting a great morphological diversity. The 150+ species in New Guinea are monophyletic, apparently derived from an Australian ancestor, and constitute a morphologically rather homogenous group. The tree backbone remains insufficiently supported under parsimony and Bayesian analyses, where shorter branches suggest a rapid sequence of major branching events.