In 1988 Zhang Yihun named and described the type species Protognathus oxyodon. The generic name was derived from Greek πρῶτος, protos, "first", and γνάθος, gnathos, "jaw". The specific name is derived from Greek ὀξύς, oxys, "sharp", and ὀδών, odon, "tooth". However, the generic name was preoccupied, already in use, by a genus of beetle, Protognathus Basilewsky 1950. The species was therefore renamed into the combinatio nova Prognathosaurus oxyodon by George Olshevsky in 1991.
Protognathosaurus is known only from a fragmentary lower jaw, holotype CV 00732 (= ChM V732) found in a layer of the Shaximiao Formation dating from the Bathonian-Callovian. The fragment consists of the front left dentary and shows eighteen tooth positions, some still containing sharp replacement teeth, after which the genus was named. Most researchers consider Protognathosaurus to be a nomen dubium.