Aspects of the phylogeny of pleurodiran turtles are contentious, particularly within the Chelidae. Morphological analyses group the long-necked Australasian Chelodina and the long-necked South American Chelus and Hydromedusa into a single clade, suggesting a common derived origin of the long neck and associated habits that predated the separation of Australia from South America. In contrast, published analyses of 12SrRNA and cytochrome b sequences suggest that the long-necked Chelodina are more closely related to the short-necked Australasian genera than to either Chelus or Hydromedusa. This paper adds partial sequences of 16S rRNA and CO1 mitochondrial genes and partial sequences of the nuclear oncogene c-mos to test a range of previous hypotheses on the phylogenetic relationships among chelid turtles. In total, 1382 nucleotides were available for each of 25 taxa after elimination of ambiguously aligned regions. These taxa included representatives of all the genera of the turtle families Chelidae and Pelomedusidae, the three sub-genera of Phrynops, and recognized sub-generic groups of Elseya and Chelodina. Of the four genes examined, 12S rRNA was the most informative, followed by c-mos with 16S rRNA and CO1 the least informative. The molecular data support the currently accepted arrangement for pelomedusid genera, that is, a sister relationship between the African Pelusios and Pelomedusa and a clade comprising the South American Peltoceplhalus and Podocnemis with the Madagascan Erymnochelys. However, there is also support for Erymnochelys and Podocnemis as sister taxa to the exclusion of Peltocephalus (bootstrap values of 69–80%) which is at odds with the most commonly accepted arrangement. The South American chelids are monophyletic (76–82%). This clade includes the long-necked Chelus and Hydromedusa, but excludes the Australasian long-necked Chelodina. Furthermore, the South American long-necked chelids are not themselves monophyletic, with 98–100% bootstrap values for the node supporting Chelus and the remaining South American chelids to the exclusion of Hydromedusa. Hence, the hypothesis of a monophyletic grouping of the long-necked genera of South America and Australasia is not supported by the molecular data. Although reciprocal monophyly of the South American and Australasian chelid faunas was the most likely and the most parsimonious arrangement in all but one analysis, bootstrap support for the monophyly of the Australasian chelids was low (52–66%). The South American chelids, Chelodina and the short-necked Australasian chelids form an unresolved trichotomy. The genera Phrynops and Elseya are paraphyletic, leading to a recommendation to elevate the three sub-genera of Phrynops to generic status and support for previous suggestions to erect a new genus for Elseya latistermum and close relatives. A revised classification of the extant Pleurodira is presented, consistent with the phylogenetic relationships that emerge from this study.