[3] Paraentelodon was named by L. K. Gabunia in 1964 basing on molars and canine teeth that were found in Oligocene sites of Benara, Georgia (Georgian SSR at the time of discovery).

[2] Although Gabunia did not explain the etymology, the name Paraentelodon is derived from the Greek para/παρα "beside" or "near", ἐντελής entelēs "complete" or "perfect" and ὀδών odōn "tooth".

The alleged indeterminate Paraentelodon species may be "Elodon transsilvanicus" (Kretzoi, 1941) from the Oligocene of Romania or a close relative, based on similar knolls on their molars.

[2] As with other entelodonts, it was an omnivore with large teeth that enabled it to crush bone and dig for tubers like its North American relatives.

[3] The jaws of Paraentelodon were found in the early Miocene Jiaozigou locality of China where a tusk of a Gomphotherium-like proboscidean was also present.