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 to the Middle Jurassic (Callovian), about 163 million years ago.

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.

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.