Adzhosuchus fuscus was named by Efimov et al. (2000). Its type specimen is PIN 4174/5, a partial skull (Incomplete skull and mandible), and it is a 3D body fossil. Its type locality is Ulan Malgait Mtn. [Ulan Malgait Fm., bed 2] [SMPE], which is in a Tithonian terrestrial sandstone/siltstone in the Ulan Malgait Formation of Mongolia.

It was recombined as Shartegosuchus fuscus by Buscalioni (2017).