Pantelosaurus is known from about 6 individuals including skulls and partial postcranial skeletons. All specimens were collected at Königin-Carola-Schacht locality, in Dresden, from the uppermost part of the Döhlen Formation, lower Rotliegend Group (Döhlen Basin), dating to the Asselian stage of the Cisuralian series, about 299–296.4 million years old.^[1][2]

Pantelosaurus was first described by von Huene (1925) as a pelycosaur. In 1940, Alfred Sherwood Romer and Llewellyn Price revised the taxonomy of pelycosaurs and synonymized Pantelosaurus with Haptodus, creating the new combination Haptodus saxonicus. After describing a new species of Haptodus in 1977, Currie (1979) synonymized all European haptodontines, as well as Cutleria wilmarthi, with the type of the genus, H. baylei. Later, Laurin (1993 and 1994) considered Haptodontinae to represent a polyphyletic grade of basal sphenacodonts, and revalidated Pantelosaurus among other genera and species. His revision has since been accepted.^[3] Only three phylogenetic analyses included Pantelosaurus. Laurin (1994), Fröbisch et al. (2011) and Benson (2012) recovered it as a basal sphenacodont, more derived than Haptodus garnettensis (Currie, 1977) or in a polytomy with it.^[1][2][4] The cladogram below shows Pantelosaurus' phylogenetic position among other synapsids following Benson (2012).^[2]

Spindler (2016) utilized use of the name Palaeohatteriidae for the clade comprising Palaeohatteria and Pantelosaurus.^[5]

Pantelosaurus was first described and named by Friedrich von Huene in 1925 and the type species is Pantelosaurus saxonicus. The generic name is derived from the Greek word pantelos "complete, finished" in reference to the nearly complete condition of the original fossil specimens, providing information on the animal's skull and most of its skeleton. The specific name is derived from the name of the Free State of Saxony in which the holotype was found.^[1]