Fossil pectoral spines belonging to this taxon were first recognized in 1822, from chalk deposits in England, by Gideon Mantell, the physician and geologist who also discovered the dinosaur Iguanodon.

During the 1870s, B. F. Mudge, a fossil collector supplying material to rival paleontologists Edward Drinker Cope and Othniel Charles Marsh, discovered a number of specimens of Protosphyraena in Niobrara exposures in Rooks and Ellis counties in Kansas and sent them back east.

Between 1873 and 1877, Cope renamed three species based on Mudge's specimens, all of which would eventually be recognized as belonging to the genus Protosphyraena: Erisichte nitida, "Portheus" gladius, and "Pelecopterus" pernicciosus.

Between 1895 and 1903, paleontologists in America and England, including Arthur Smith Woodward (1895), Loomis (1900), O. P. Hay (1903), in a series of important works, reviewed the genus, adding much to our understanding of this fish.

This preservational bias can be explained by the fact that the skeleton of Protosphyraena was less ossified than that of most bony fishes and tended to be torn apart by scavengers or decay before burial and fossilization (Everhart, 2005; p. 93).