Cyclotosaurus randalli was named by Welles (1947). Its type specimen is UCMP 36188, a partial skull ( a circumotic fragment of a skull roof), and it is a 3D body fossil. Its type locality is Holbrook quarry, UCMP V3922, which is in an Aegean/Bithynian fine channel fill siltstone in the Moenkopi Formation of Arizona.

It was considered a nomen dubium by Schoch and Milner (2000); it was recombined as Eocyclotosaurus randalli by Damiani (2001).