The evolution of blanid amphisbaenians (Mediterranean worm lizards) is mainly inferred based on molecular studies, despite their fossils are common in Cenozoic European localities. This is because the fossil record exclusively consists in isolated elements of limited taxonomic value. We describe the only known fossil amphisbaenian skull from Europe - attributed to Blanus mendezi sp. nov. (Amphisbaenia, Blanidae) - which represents the most informative fossil blanid material ever described. This specimen, from the Middle Miocene of Abocador de Can Mata (11.6 Ma, MN7+8) in the Vallès-Penedès Basin (Catalonia, NE Iberian Peninsula), unambiguously asserts the presence of Blanus in the Miocene of Europe. This reinforces the referral to this genus of the previously-known, much more incomplete and poorly-diagnostic material from other localities of the European Neogene. Our analysis - integrating the available molecular, paleontological and biogeographic data - suggests that the new species postdates the divergence between the two main (Eastern and Western Mediterranean) extant clades of blanids, and probably precedes the split between the Iberian and North-Western African subclades. This supports previous paleobiogeographic scenarios for blanid evolution and provides a significant minimum divergence time for calibrating molecular analyses of blanid phylogeny.