In 1845 amateur geologists William Guybon Atherstone and Andrew Geddes Bain near Dassieklip, Cape Province, in the valley of the Bushmans River found a number of fossils. Bain in 1849 and 1853 sent some to the British paleontologist Richard Owen for identification. Among them was the upper jaw of what Bain thought was a dinosaur that he informally had indicated as the "Cape Iguanodon"; the site likewise was named "Iguanodonhoek". In 1857 Atherstone published about the find, but in 1871 lamented that it as yet had received no attention in London. Only in 1876 Owen named a series of specimens as Anthodon serrarius. Anthodon means "flower tooth".
In 1909 the South-African paleontologist Robert Broom visited the collection of the British Museum of Natural History. He concluded that Owen had mixed the fossils of two entirely different species: those of a member of the Pareiasauria and a dinosaur jaw. Broom kept the name Anthodon for the pareiasaur and identified the dinosaur fossil as belonging to the genus Palaeoscincus, naming in 1910/1912 the new species Paleoscincus africanus'.
In 1929 Baron Franz Nopcsa also studied the specimen. Unaware of Broom's publication he basically drew the same conclusions but also named a new genus coining for the dinosaur the name Paranthodon Oweni. The generic name means "near" or "besides" (para in Greek) Anthodon. The specific name honours Owen. In his publication Nopcsa by mistake also used the spelling variant Paranthodon Owenii. By present conventions the name should be written as Paranthodon oweni.
Only in 1978 Walter Coombs correctly combined both names into a Paranthodon africanus.
The holotype, BMNH 47338, was found in a layer of the Kirkwood Formation dating from the Berriasian-Valanginian. It consists of the back of the snout, containing the maxilla with teeth, the posterior caudodorsal ramus of the premaxilla and part of the nasals. The snout is elongated but not extremely so and convex on top; the back of the premaxilla is long and broad; the external nares are large. The teeth have a prominent primary ridge.
Paleoscincus is an ankylosaur genus. Nopcsa however, thought Paranthodon was a member of the Stegosauridae, related to Stegosaurus and Kentrosaurus. After 1929 most scientists nevertheless tended to classify Paranthodon as an ankylosaur. Only in 1981 Peter Galton established it was indeed a stegosaurid. If so, it would be about five metres long and be the second stegosaur discovered, after Regnosaurus, besides being the first dinosaur found in South-Africa. According to a recent analysis it would be closely related to Tuojiangosaurus, Loricatosaurus and Stegosaurus.