Tengrisaurus starkovi, gen. et sp. nov., is described based on three caudal vertebrae from the Lower Cretaceous (Barremian?) Murtoi Formation at Mogoito locality, near Gusinoe Lake in Buryatia, Russia. The new taxon is characterized by strongly procoelous anterior and middle caudal vertebrae, with strongly developed pre-epipophyses, highly pneumatic neural spine, and solid bone structure of the centrum. The reweighted phylogenetic analysis places the new taxon as a non-saltasaurid lithostrotian titanosaur (Sauropoda). This is one of the oldest fossil records of Lithostrotia and Titanosauria, which suggests a long and unexplored evolution of titanosaurs in the Early Cretaceous of Asia.