Phylogenetic relationships and taxonomy of the short-necked turtles of the genera Elseya, Myuchelys, and Emydura in Australia and New Guinea have long been debated as a result of conflicting hypotheses supported by different data sets and phylogenetic analyses. To resolve this contentious issue, we analyzed sequences from two mitochondrial genes (cytochrome b and ND4) and one nuclear intron gene (R35) from all species of the genera Elseya, Myuchelys, Emydura, and their relatives. Phylogenetic analyses using three methods (maximum parsimony, maximum likelihood, and Bayesian inference) produce a single, well resolved, and strongly corroborated hypothesis, which provides support for the three genera, with the exception that the genus Myuchelys is paraphyletic-Myuchelys purvisi is the sister taxon to the remaining Elseya, Myuchelys and Emydura. A new genus is proposed for the species Myuchelys purvisi to address this paraphyletic relationship. Time-calibration analysis suggests that diversification of the group in Australia coincides with periods of aridification in the late Eocene and between the mid-Miocene and early Pliocene. Other speciation events occurred during the faunal exchange between Australia and the island of New Guinea during the late Miocene and early Pliocene. Lineages distributed in New Guinea are likely influenced by the complex geologic history of the island, and include cryptic species diversity.