The Ypresian Cambay Shale Formation at Vastan, Mangrol, and Tadkeshwar lignite mines in Gujarat, western India, has yielded a rich vertebrate fauna including madtsoiid, palaeophiid, booid, and colubroidean-like snakes. The latter are particularly abundant, but their systematic affinities are difficult to resolve. Here we describe new specimens of the colubroidean-like snake Thaumastophis missiaeni, including anterior, middle, and posterior trunk vertebrae, as well as caudal vertebrae. The combination of primitive and derived caenophidian and colubroidean vertebral characters confirms Thaumastophis as the earliest known stem-colubriform snake while Procerophis, from the same beds, is more derived and considered to represent a crown-Colubriformes. Additionally, Thaumastophis shares with Renenutet enmerwer from the late Eocene of Egypt a unique combination of vertebral characters that suggests an exchange with North Africa was possible along the southern margin of the Neotethys. We erect the new family Thaumastophiidae for Thaumastophis and Renenutet on the basis of their shared derived vertebral morphology.