The New Guinea freshwater turtle, Elseya novaeguineae (senu lato) is a long-term, widespread resident of New Guinea and has been subject to substantial vicariance in one of the most geologically dynamic regions on earth. Thus, it should come as no surprise that the taxonomy of this turtle is poorly resolved. Elseya novaeguineae has long been recognized as a species complex, though which elements of this taxon warrant recognition as separate species has been debated. In this paper, we restrict Elseya novaeguineae to the Birds Head region of New Guinea, west of the Langguru Thrust and Fold Belt; we resurrect from synonymy Elseya schultzei for the populations north of the Central Ranges; and we describe a new species for the populations to the south of the Central Ranges. We revisit the classification of the genus Elseya throughout its range in the light of our work and recently published reports, and erect three subgenera that recognize the three major clades within this genus. Subgenus Elseya is the nominate subgenus, to which we assign Elseya dentata, E. branderhorsti and undescribed E. sp. aff. dentata [Sth Alligator]. Elseya novaeguineae, E. schultzei and our new species are assigned to a new subgenus, Hanwarachelys. Species of northern and eastern Queensland, E. albagula, E. irwini, E. lavarackorum and the fossil taxa E. uberrima and E. nadibajagu, are assigned to subgenus Pelocomastes, resurrected from synonymy.