Coelodontognathus donensis was named by Ochev (1967). Its type specimen is PIN 4173/129 (formerly SGU 104/3103), a mandible (right dentary), and it is a 3D body fossil. Its type locality is Lipovskaya gully (Donskaya Luka), which is in an Olenekian terrestrial horizon in the Lipovskaya Formation of the Russian Federation.