Background: Lepidosauria (lizards, snakes, tuatara) is a globally distributed and ecologically important group of over 9,000 reptile species. The earliest fossil records are currently restricted to the Late Triassic and often dated to 227 million years ago (Mya). As these early records include taxa that are relatively derived in their morphology (e.g. Brachyrhinodon), an earlier unknown history of Lepidosauria is implied. However, molecular age estimates for Lepidosauria have been problematic; dates for the most recent common ancestor of all lepidosaurs range between approximately 226 and 289 Mya whereas estimates for crown-group Squamata (lizards and snakes) vary more dramatically: 179 to 294 Mya. This uncertainty restricts inferences regarding the patterns of diversification and evolution of Lepidosauria as a whole. Results: Here we report on a rhynchocephalian fossil from the Middle Triassic of Germany (Vellberg) that represents the oldest known record of a lepidosaur from anywhere in the world. Reliably dated to 238--240 Mya, this material is at least 11 million years older than previously known lepidosaur records and is older than some but not all molecular clock estimates for the origin of lepidosaurs. Using RAG1 sequence data from 77 extant taxa and the new fossil specimens two of several calibrations, we estimate that the most recent common ancestor of Lepidosauria lived at least 242 Mya (238--249.5), and crown-group Squamata originated around 193 Mya (176--213). Conclusion: A Early/Middle Triassic date for the origin of Lepidosauria disagrees with previous estimates deep within the Permian and suggests the group evolved as part of the faunal recovery after the end-Permain mass extinction as the climate became more humid. Our origin time for crown-group Squamata coincides with shifts towards warmer climates and dramatic changes in fauna and flora. Most major subclades within Squamata originated in the Cretaceous postdating major continental fragmentation. The Vellberg fossil locality is expected to become an important resource for providing a more balanced picture of the Triassic and for bridging gaps in the fossil record of several other major vertebrate groups.