In 1897 French paleontologist Henri-Émile Sauvage referred a tail vertebra from the Kimmeridgian of Portugal, present in the collection of the Musée Géologique du Boulonnais at Boulogne-sur-Mer in France, to Iguanodon prestwichii, a herbivorous iguanodont.
In 1928 Baron Franz Nopcsa recognised the fossil to be the vertebra of a theropod instead. He decided to name it as the genus Teinurosaurus. The name is derived from Greek teinein, "to stretch", and oura, "tail", referring to the elongated form. However, by a mistake of the printer, the footnote in which the new name was mentioned was not placed at the end of the section referring to the fossil but adjacent to a citation of Saurornithoides Osborn 1924, giving the false impression Nopcsa intended to rename the latter genus. After having discovered the typographical error, Nopcsa in 1929 added an addendum to the article, correcting the mistake.
In 1932 German paleontologist Friedrich von Huene again named the fossil, giving it the species name Caudocoelus sauvagei. "Caudocoelus" means "hollow tail" in Latin. The specific epithet honours Sauvage. The name Teinurosaurus was largely forgotten or not even understood to be a synonym of Caudocoelus, until in 1969 John Ostrom revealed its priority. Ostrom also pointed out that Nopcsa had not provided a specific name. In 1978 George Olshevsky was the first to combine the two names, making Teinurosaurus sauvagei (von Huene 1932) Olshevsky 1978 vide Nopcsa 1928 emend. 1929 a valid species name.
The holotype, once having the inventory number MGB 500 but later lost, was a distal caudal vertebra, 152 millimetres long. The species was by von Huene considered a member of the Coeluridae but is now generally seen as a nomen dubium, Neotheropoda incertae sedis.