This post was originally posted December 6, 2014 and removed as a courtesy to Sebastian Apesteguia, who mentioned their team came to a similar conclusion with regard to snakes and is awaiting publication December 29. This is a case of convergent discovery and attests to the validity of methods used here.
A few years ago
Bolet and Evans (2012) introduced us to one of the smallest fossil lizards ever found, Jucaraseps grandpes (Fig. 1).

Figure 1. Jucaraseps in situ. Click to enlarge. This tiny long lizard is in the lineage of terrestrial snakes. Note the actual size of this lizard is about a third of that seen here at 72 dpi.
from the Bolet and Evans 2012 conclusion:
“Jucaraseps lies at the lower end of the modern lizard size range and demonstrates that very small-bodied lizards existed in the Early Cretaceous. Its slender, elongated body is reminiscent of many small living scincid lizards and some gymnophthalmids, and Jucaraseps is likely to have had a similar lifestyle. Phylogenetic analysis places Jucaraseps on the stem of a traditional monophyletic Scleroglossa (sensu Estes et al. 1988 and Conrad 2008; contra Townsend et al. 2004 and Vidal and Hedges 2005), which would be consistent with the frequency of body elongation ⁄ limb reduction within this group. However, further material (especially of the skull) may lead to a refinement of this position, as may more global molecular ⁄morphological analyses of Squamata as a whole.”
That basal position in the Conrad 2008 tree nests Jucaraseps with Eichstaettisaurus (Fig. 2) in the Bolet and Evans (2012) tree. The large reptile tree (still not updated) nests Jucaraseps and Eichstaettisaurus with Adriosaurus and snakes. Note the similarity between Adriosaurus and Jucaraseps, especially in the rib shape This shape is carried forward in the basal snake, Pachyrhachis.

Figure 2. Snake ancestor sisters to two scales. Above Jucaraseps with Eichstaettisaurus. Below both with Adriosaurus.
An important abstract on snake origins: Caldwell, et al. 2014.
“Previous reports identifying the oldest known fossil snake specimens were based on isolated vertebrae from sediments in North Africa and North America (Albian to Cenomanian: ~105-100 Ma). Bathonian (Middle Jurassic; 167 Ma) to Barremian (Lower Cretaceous, 143 Ma) squamate fossils from Colorado, Portugal and England are here recognized as the geologically oldest known fossil snakes, extending the fossil record of snakes by approximately 70 million years. The cranial, dental and postcranial anatomy of these well-preserved but fragmentary fossil snakes indicates that the basic architecture of the modern snake skull and dentition had evolved as early as 167 million years ago.
“These oldest fossil snakes show unmistakable features of the snake skull (e.g., recurved
teeth with labial and lingual carinae, teeth attached to margins of distinct alveoli with interdental plates, long toothed suborbital ramus of maxillae, laterally emarginated dentary, well developed descensus frontalis with suboptic shelves). There are also several lizard-like features (e.g., pronounced subdental shelf/gutter, multiple mental foramina on the dentary) as would be expected in early snakes not long after their divergence from a lizard ancestor. These vertebrae show critical similarities to much younger Mesozoic snakes such as Coniophis, Dinilysia, Najash, Pachyrhachis, Simoliophis, etc., and to all extant snakes (e.g., wide neural arch, low neural spines, prominent arcual ridges well developed zygosphenes, zygosphenal tectum with festooned anterior margin, condyles and cotyles are circular and offset from centrum ventral margins that are strongly rectangular in outline, with a squared margin immediately anterior to the condyle). The paleobiogeography (e.g., islands in epicontinental seas and continental Laurasia) and paleoecology (e.g., coal swamps, lacustrine and fluvial systems) of these earliest snakes is diverse and complex, and suggests that snakes had already undergone significant habitat differentiation and geographic radiation by the mid-Jurassic. Phylogenetic analysis recovers these early snakes as basal to all other snakes (fossil and modern). The snake origins debate, both in terms of ancestral forms and environments, is strongly impacted as these most ancient snakes show unexpected anatomies and paleoecologies.”
That will be a very interesting paper!
Jucaraseps lived in the Early Cretaceous, but sister taxa must have lived in the Jurassic, prior to the origin of the most primitive snakes. Jucaraseps contemporaries include many protosquamates. Jucaraseps is thus a rare representative of the squamates in the Early Cretaceous.
References
Bolet A and Evans SE 2012. A tiny lizard (Lepidosauria, Squamata) from the lower Cretaceous of Spain. Palaeontology 55:491-500.
Caldwell M, Nydam R, Palci A and Apesteguía S 2014. The oldest known fossil snakes: a tempera range extension of 70 million years. Journal of Vertebrate Paleontology abstracts.