The oldest record of the group is dated to the Middle Triassic around 238 to 240 million years ago, and they had achieved global distribution by the Early Jurassic.

Once representing the world's dominant group of small reptiles, many of the niches occupied by lizards today were held by rhynchocephalians during the Triassic and Jurassic.

While the modern tuatara is primarily insectivorous and carnivorous, the diversity of the group also included the herbivorous eilenodontines, and there were other rhynchocephalians with specialised ecologies like the durophagous sapheosaurs.

They remained misclassified until 1867, when Albert Günther of the British Museum noted features similar to birds, turtles, and crocodiles.

He proposed the order Rhynchocephalia (from Ancient Greek ῥύγχος (rhúnkhos) 'beak' and κεφαλή (kephalḗ) 'head', meaning "beak head") for the tuatara and its fossil relatives.

[4] Studies in the 1970s and 1980s demonstrated that rhynchosaurs were unrelated, with computer-based cladistic analysis conducted in the 1980s providing a robust diagnosis for the definition of the group.

[8] Rhynchocephalia and their sister group Squamata (which includes lizards, snakes and amphisbaenians) belong to the superorder Lepidosauria, the only surviving taxon within Lepidosauromorpha.

Squamates and rhynchocephalians have a number of shared traits (synapomorphies), including fracture planes within the tail vertebrae allowing caudal autotomy (loss of the tail when threatened), transverse cloacal slits, an opening in the pelvis known as the thyroid fenestra, the presence of extra ossification centres in the limb bone epiphyses, a knee joint where a lateral recess on the femur allows the articulation of the fibula, the development of a sexual segment of the kidney, and a number of traits of the feet bones, including a fused astralago-calcaneun and enlarged fourth distal tarsal, which creates a new joint, along with a hooked fifth metatarsal.

[17][18] While often lacking a complete temporal bar, the vast majority of rhynchocephalians have a posteriorly directed process (extension) of the jugal bone.

This differs from the condition found in most lizards (except acrodontans), which have pleurodont teeth which are attached to the shelf on the inward-facing side of the jaw, and are replaced throughout life.

This arrangement, which is unique among amniotes, permits three point bending of food items,[26] and in combination with propalinal movement (back and forward motion of the lower jaw) allows for a shearing bite.

The unranked clade Neosphenodontia is defined as the most inclusive clade containing Sphenodon but not Clevosaurus hudsoni, which is supported by the presence of six synapomorphies, including the increased relative length of the antorbital region of the skull (the part of the skull forward of the eye socket), reaching 1/4 to 1/3 of the total skull length, the posterior (hind) edge of the parietal bone is only slightly curved inward, the parietal foramen is found at the same level or forward of the anterior border of the supratemporal fenestra (an opening of the skull), the palatine teeth are further reduced from the condition in eusphenodontians to a single lateral tooth row, the number of pterygoid tooth rows are reduced to one or none, and the posterior border of the ischium is characterised by a distinctive process.

[18] The following is a cladogram of Rhynchocephalia after DeMar et al. 2022 (based on maximum parsimony, note that cladogram collapses into a polytomy under Bayesian analysis):[20] Gephyrosaurus bridensis Diphydontosaurus avonis Planocephalosaurus robinsonae Rebbanasaurus jaini Godavarisaurus lateefi Theretairus antiquus Polysphenodon mulleri Opisthiamimus gregori Clevosaurus convallis Clevosaurus brasiliensis Clevosaurus hadroprodon Clevosaurus bairdi Clevosaurus hudsoni Clevosaurus cambrica Brachyrhinodon taylori Colobops noviportensis Sphenodon punctatus (tuatara) Cynosphenodon huizachalensis Sphenovipera jimmysjoyi Kawasphenodon expectatus Kawasphenodon peligrensis Pelecymala robustus Fraserosphenodon latidens Opisthias rarus Eilenodon robustus Sphenotitan leyesi Toxolophosaurus cloudi Priosphenodon avelasi Homoeosaurus maximiliani Kallimodon pulchellus Sigmala sigmala Vadasaurus herzogi Palaeopleurosaurus posidonae Pleurosaurus goldfussi Pleurosaurus ginsburgi Kallimodon cerinensis Sapheosaurus thiollierei Ankylosphenodon pachyostosus Oenosaurus muehlheimensis Cladogram after Simoes et al. 2022 (based on Bayesian inference analysis):[18] †Diphydontosaurus †Planocephalosaurus †Clevosaurus †Homoeosaurus †Palaeopleurosaurus †Derasmosaurus †Pleurosaurus †Leptosaurus †Kallimodon †Piocormus †Oenosaurus †Sapheosaurus †Sphenotitan †Eilenodon †Toxolophosaurus †Priosphenodon †Navajosphenodon †Cynosphenodon †Sphenofontis †Kawasphenodon Sphenodon (tuatara) The fossil record of rhynchocephalians demonstrates that they were a diverse group that exploited a wide array of ecological niches.

[44][37] Sphenovipera from the Jurassic of Mexico has been suggested to have been venomous, based on presence of grooves on two enlarged teeth at the front of the lower jaw[45] though this interpretation has been questioned by other authors.

[45] The body of Pamizinsaurus from the Early Cretaceous of Mexico was covered in osteoscutes, similar to those of helodermatid lizards like the Gila monster, which is unique among known sphenodontians, which probably served to protect it against predators.

[48] During the Jurassic, rhynchocephalians were the dominant group of small reptiles globally,[49] reaching their apex of morphological diversity during this period, including specialised herbivorous and aquatic forms.

[51] The youngest undoubted remains of rhynchocephalians outside of New Zealand are those of the sphenodontid Kawasphenodon peligrensis from the early Paleocene (Danian) of Patagonia, shortly after the Cretaceous–Paleogene extinction event.

[57] Indeterminate sphenodontine jaw fragments bearing teeth are known from the early Miocene (19–16 million years ago) St Bathans fauna, New Zealand, that are indistinguishable from those of the living tuatara.