Pan-trionychids or softshell turtles are a highly specialized and widespread extant group of aquatic taxa with an evolutionary history that goes back to the Early Cretaceous. The earliest pan-trionychids had already fully developed the "classic" softshell turtle morphology and it has been impossible to resolve whether they are stem members of the family or are within the crown. This has hindered our understanding of the evolution of the two basic body plans of crown-trionychids. Thus it remains unclear whether the more heavily ossified shell of the cyclanorbines or the highly reduced trionychine morphotype is the ancestral condition for softshell turtles. A new pan-trionychid from the Early Cretaceous of Zhejiang, China, Perochelys hengshanensis sp. nov., allows a revision of softshell-turtle phylogeny. Equal character weighting resulted in a topology that is fundamentally inconsistent with molecular divergence date estimates of deeply nested extant species. In contrast, implied weighting retrieved Lower Cretaceous Perochelys spp. and Petrochelys kyrgyzensis as stem trionychids, which is fully consistent with their basal stratigraphic occurrence and an Aptian-Santonian molecular age estimate for crown-trionychids. These results indicate that the primitive morphology for soft-shell turtles is a poorly ossified shell like that of crown-trionychines and that shell re-ossification in cyclanorbines (including re-acquisition of peripheral elements) is secondary.