Veterupristisaurus is known from the holotype specimen MB R 1938, an isolated middle caudal vertebra. Two partially fused posterior middle caudal vertebrae, MB R 2166, from the same locality as the holotype, are referred to this genus and most probably came from the same individual. The anterior caudal vertebra, MB R 1940, may also represent this genus. The holotype was collected in the St (EH) locality of the Tendaguru in German East Africa, from the Middle Dinosaur Member of the Tendaguru Formation, dating to the late Kimmeridgian to earliest Tithonian faunal stage of the Late Jurassic, about 154-150 million years ago. It was originally referred to Ceratosaurus? roechlingi by Werner Janensch.
Veterupristisaurus was a large bipedal animal. The length of the holotype vertebra is about 123 mm (4.8 in), thus Veterupristisaurus has been estimated to have been about 8.5 m (28 ft)-10 m (33 ft) in length, based on the more complete and closely related Acrocanthosaurus. Whether the individual represented by the holotype represents an adult individual cannot be determined based on the available material. It is diagnosed by a spinoprezygapophyseal lamina in the middle caudal vertebrae extending anteriorly to the midwidth of the base of the prezygapophysis and being flanked laterally by a short, parallel lamina extending from the lateral margin of the prezygapophysis posteriorly. Thus, Rauhut considered a sister-group relationship between Veterupristisaurus and Acrocanthosaurus within the Carcharodontosauridae.
Veterupristisaurus was first named by Oliver W. M. Rauhut in 2011 and the type species is Veterupristisaurus milneri. The generic name translates as “old shark lizard”. It refers to the fact that Veterupristisaurus is currently the oldest known representative of the “shark-toothed lizards”, the Carcharodontosauridae. The specific name honours the paleontologist Angela C. Milner.