We present a phylogenetic hypothesis and novel, rank-free classification for all extant species of softshell turtles (Testudines:Trionychidae). Our data set included DNA sequence data from two mitochondrial protein-coding genes and a approximately 1-kb nuclear intron for 23 of 26 recognized species, and 59 previously published morphological characters for a complimentary set of 24 species. The combined data set provided complete taxonomic coverage for this globally distributed clade of turtles, with incomplete data for a few taxa. Although our taxonomic sampling is complete, most of the modern taxa are representatives of old and very divergent lineages. Thus, due to biological realities, our sampling consists of one or a few representatives of several ancient lineages across a relatively deep phylogenetic tree. Our analyses of the combined data set converge on a set of well-supported relationships, which is in accord with many aspects of traditional softshell systematics including the monophyly of the Cyclanorbinae and Trionychinae. However, our results conflict with other aspects of current taxonomy and indicate that most of the currently recognized tribes are not monophyletic. We use this strong estimate of the phylogeny of softshell turtles for two purposes: (1) as the basis for a novel rank-free classification, and (2) to retrospectively examine strategies for analyzing highly homoplasious mtDNA data in deep phylogenetic problems where increased taxon sampling is not an option. Weeded and weighted parsimony, and model-based techniques, generally improved the phylogenetic performance of highly homoplasious mtDNA sequences, but no single strategy completely mitigated the problems of associated with these highly homoplasious data. Many deep nodes in the softshell turtle phylogeny were confidently recovered only after the addition of largely nonhomoplasious data from the nuclear intron.