Amphisbaenia is a speciose clade of fossorial lizards characterized by a snake-like body and a strongly reinforced skull adapted for head-first burrowing. The evolutionary origins of amphisbaenians are controversial, with molecular data uniting them with lacertids, a clade of Old World terrestrial lizards, whereas morphology supports a grouping with snakes and other limbless squamates. Reports of fossil stem amphisbaenians have been falsified, and no fossils have previously tested these competing phylogenetic hypotheses or shed light on ancestral amphisbaenian ecology. Here we report the discovery of a new lacertid-like lizard from the Eocene Messel locality of Germany that provides the first morphological evidence for lacertid-amphisbaenian monophyly on the basis of a reinforced, akinetic skull roof and braincase, supporting the view that body elongation and limblessness in amphisbaenians and snakes evolved independently. Morphometric analysis of body shape and ecology in squamates indicates that the postcranial anatomy of the new taxon is most consistent with opportunistically burrowing habits, which in combination with cranial reinforcement indicates that head-first burrowing evolved before body elongation and may have been a crucial first step in the evolution of amphisbaenian fossoriality.