An additional anterior caudal vertebra of a titanosaurian sauropod Tengrisaurus starkovi from the Lower Cretaceous (Barremian–Aptian) Murtoi Formation of Transbaikalia, Asiatic Russia, reveals new morphological details of this taxon. The new characters include dorsoventrally compressed cotyle and condyle of the centrum and a prominent ridge separating the condyle from the rest of the centrum with the ventral triangular plate (autapomorphy). Parsimony phylogenetic analysis places Tengrisaurus in the predominantly Gondwanan clade Colossosauria + Epachthosaurus on the strict consensus tree and as the sister taxon to the Colossosauria on 66% of the most parsimonious trees. Among Colossosauria, Tengrisaurus is similar with Normanniasaurus from the Albian of France by having a dorsoventrally compressed condyle circumscribed by a distinct ridge, a distinct depression anteroventral to the postzygapophysis, and a deep depression within the postspinal fossa. This discovery suggests that ancestors of the clade Colossosauria were widely distributed in Eurasia during the Early Cretaceous and the clade becomes restricted to the southern continents in the Late Cretaceous.