Understanding the origin and early evolution of snakes from lizards depends on accurate morphological knowledge of the skull in basal lineages, but fossil specimens of archaic snakes have been rare, and either fragmentary or difficult to study as a result of compression by enclosing sediments. A number of Cenozoic fossil snakes from Australia have vertebral morphology diagnostic of an extinct group, Madtsoiidae, that was widespread in Gondwana from mid-Cretaceous (Cenomanian) to Eocene times, and also reached Europe in the late Cretaceous period. Despite this long history, only about half the skull is known from the best-known species Wonambi naracoortensis, and the few known cranial elements of other species have added little further evidence for phylogenetic relationships. Conflicting hypotheses have been proposed for their relationships and evolutionary significance, either as basal ophidians with many ancestral (varanoid- or mosasaur-like) features, or advanced (macrostomatan) alethinophidians of little relevance to snake origins. Here I report two partial skeletons referred to Yurlunggur, from the late Oligocene and early Miocene of northern Australia, which together represent almost the complete skull and mandible. The exceptionally preserved skulls provide new evidence linking Yurlunggur with Wonambi and other madtsoiids, falsifying predictions of the macrostomatan hypothesis, and supporting the exclusion of Madtsoiidae from the clade including all extant snakes.