The genus has been described by the German paleontologist Rupert Wild in 1978. The type species is Peteinosaurus zambellii. The genus name is derived from Greek peteinos, "winged" and sauros, "lizard", the latter being used to indicate any saurian. The specific name, zambellii, honours Rocco Zambelli, the curator of the Bergamo natural history museum.
Peteinosaurus was one of the smallest pterosaurs. Peteinosaurus had a wingspan of around 60 cm (24 in), and its weight was less than that of a common blackbird.
Three fossils have been found near Cene, Italy. The first fossil, the holotype MCSNB 2886, is fragmentary and disarticulated. The second, the articulated paratype MCSNB 3359, lacks any diagnostic features of Peteinosaurus and thus might be a different species. This paratype has a long tail (20 cm) made more stiff by long extensions of the vertebrae; this feature is common among pterosaurs of the Triassic. The third example is MCSNB 3496, another fragmentary skeleton. All specimens are those of subadults and of none has the skull been preserved.
Like most pterosaurs, Peteinosaurus had bones that were strong but very light. Peteinosaurus is trimorphodontic, with three types of conical teeth. An insectivorous lifestyle has been attributed to Peteinosaurus. The fifth toe of Peteinosaurus was long and clawless. Its joint allowed it to flex in a different plane than the other phalanges in order to control the cruropatagium, as seen preserved in the specimen of Sordes pilosus PIN 2585.3.