A reexamination of the holotype of 'Plesiochelys' tatsuensis Yeh, 1963, from the Late Jurassic of China, allows us to establish previously unknown characters of this species. A phylogenetic analysis places 'P.' tatsuensis on the stem of Trionychia, near the clades Adocidae and Nanhsiungchelyidae. Given the hypothesized phylogenetic position of 'P.' tatsuensis, a new genus, Yehguia gen. nov., is erected for this species. The phylogenetic position of Y. tatsuensis pushes the origin of the crown clade Cryptodira into the Late Jurassic. This is remarkable in light of recent studies that moved the origin of crown group turtles (Testudines) from the Triassic to the Late Jurassic. This means that the establishment of basal cryptodiran lineages must have quickly followed the origin of Testudines in the Late Jurassic. The fact that the most ancient fossil Cryptodira is hypothesized to be on the stem of Trionychia is concordant with recent molecular hypotheses that place Trionychia as the most basal extant lineage of Cryptodira. Finally, our results further highlight that the Late Jurassic of China is important for understanding the earliest evolution of cryptodiran turtles.