In 1969 Argentine paleobotanist Rafael Herbst in the province Neuquén at Picun Leufú dug up a piece of sandstone holding a number of disarticulated bones of a small reptile. At the time it was assumed the rock dated from the Middle Jurassic (Callovian), about 163 million years ago.
In 1974/1975 paleontologist Rodolfo Magín Casamiquela named the find as a new genus. The type species is Herbstosaurus pigmaeus. The genus name honours Herbst and connects his name to Greek sauros, "lizard", a usual element in the name of dinosaurs — Casamiquela assumed the new genus was a theropod dinosaur. The specific name is derived from Greek pygmaios, "dwarf": it was thought the form presented a small Compsognathus-like coelurosaurian belonging to the Coeluridae and one of the smallest dinosaurs then known.
The holotype is CTES-PZ-1711, consisting of a sacrum, pelvic elements and both femora. The dispersed bones are compressed, crushed by the weight of the layers above.
Casamiquela had already indicated that the new species was very distinct because of an atypically long ilium and short ischium. In 1978 John Ostrom, while reviewing the relations of Compsognathus, concluded that these qualities were best explained by the hypothesis that Herbstosaurus was not a dinosaur but a pterosaur, for which such proportions are normal. The new identification allowed some fragmentary pterosaur material found in the same layers to be referred to Herbstosaurus, among which a wing bone.
The phylogenetic position of Herbstosaurus has proven difficult to determine with no consensus developing. In 1981 Peter Galton stated it was a member of the Pterodactyloidea. Robert Carroll in his 1988 general textbook on vertebrate paleontology narrowed that down to the Pterodactylidae. Peter Wellnhofer however, in 1991 suggested it was not a pterodactyloid but a more basal pterosaur, in view of the form of the pelvis. In 1996 David Unwin concluded Herbstosaurus was a basal member of the Dsungaripteroidea. This was again doubted by Laura Codorniú and Zulma Gasparini in 2007.
Herbstosaurus has generated a special interest because it was possibly one of the earliest pterodactyloids known. However, it was later determined it had been found in the Vaca Muerta formation from the Upper Jurassic (Tithonian).