Sauropterygia was a taxonomically and ecomorphologically diverse clade of Mesozoic marine reptiles spanning the Early Triassic to the Late Cretaceous. Sauropterygians are traditionally divided into two groups representing two markedly different body plans – the short-necked, durophagous Placodontia and the long-necked Eosauropterygia – whereas Saurosphargidae, a small clade of armoured marine reptiles, is considered as the sauropterygian sister-group. However, the early evolutionary history of sauropterygians and their phylogenetic relationships with other groups within Diapsida are still incompletely understood. Here, we report a new saurosphargid from the Early Triassic of South China, representing the earliest known occurrence of the clade. An updated phylogenetic analysis focussing on the interrelationships within diapsid reptiles recovers saurosphargids as nested within sauropterygians, forming a clade with eosauropterygians to the exclusion of placodonts. Furthermore, a clade comprising Eusaurosphargis and Palatodonta is recovered as the sauropterygian sister-group. The phylogenetic position of several Early and Middle Triassic sauropterygians of previously uncertain phylogenetic affinity, such as Atopodentatus, Hanosaurus, Majiashanosaurus and Corosaurus, is also clarified, elucidating the early evolutionary assembly of the sauropterygian body plan. Finally, our phylogenetic analysis recovers Testudinata and Archosauromorpha within Archelosauria, a result strongly supported by molecular data, but until now rarely recovered by any phylogenetic analysis using a morphology-only data set. Our study provides evidence for the rapid diversification of sauropterygians in the aftermath of the Permo-Triassic mass extinction event and emphasises the importance of broad taxonomic sampling in reconstructing phylogenetic relationships among extinct taxa.