Sineoamphisbaena hexatabularis Wu et al., 1993 is the earliest known amphisbaenian represented by well-preserved cranial and postcranial material. It reveals a mosaic of generalized lizard-like features and amphisbaenian characters. Most distinctive of the latter are features of cranial consolidation adaptive for a fossorial way of life. Phylogenetic analyses strongly confirm the monophyly of the Amphisbaenia inclusive of S. hexatabularis. The Amphisbaenia is diagnosed by a suite of apomorphic characters. The available evidence suggests a probable Amphisbaenia–Macrocephalosauridae relationship within the Scincomorpha. This is supported primarily by the unique modifications of the palate and temporal region of the skull. It is argued here that the Amphisbaenia evolved in Central Asia during the Cretaceous, in response to the transition from a perennial lacustrine environment to a dry, semiarid eolian environment. The relatively primitive morphology indicates that S. hexatabularis was not permanently subterranean. The further derived modifications of later forms are associated with tunneling in an environment of more compact soils.