The fossil history of worm lizards in Eastern Europe is very patchy because of the small number of localities and the fragmentary vertebral material available. A new record of the genus Blanus from the late Miocene of the Egorovka1 and 2 localities in Ukraine is reported here. Based on its dental morphology, Blanus from Egorovka differs from all extinct species of the genus and from the extant B. cinereus complex. It is most closely related to the Eastern clade of Blanus (B. strauchi complex) in having enlarged second and small third dentary teeth. Blanus from Egorovka is the second fossil record of the B. strauchi complex and the first record of the Eastern clade outside of its current geographical range. It indicates a wider past range of the Eastern European Blanus, including the northern Black Sea coastal area.