From 1964 dinosaur fossils were excavated in the Junggar Basin of Xinjiang. In 1973 a number of these were described by paleontologist Dong Zhiming, among them the bones of a small theropod which he named Tugulusaurus faciles. The generic name refers to the Tugulu Group. The specific name is derived from Latin facilis, here with the meaning of "easily moving", referring to the agility of the animal as indicated by its "delicate bones".
The holotype, IVPP V4025, was found in layers of the Lianmuqin Formation dating from the Barremian–Albian. It consists of a partial skeleton including four partial tail vertebrae, much of the left leg and part of the right, the first fingers of both hands, and a rib. The femur has a length of about 215 millimetres (8.5 in). The left first metacarpal is very short: 26 millimetres (1.0 in). The skeleton represents the only remains of the species that have ever been discovered.
Originally classified by Dong as a member of the Ornithomimidae within the Coelurosauria, it was often considered a nomen dubium. However, in 2005 Oliver Rauhut and Xu Xing concluded that it is a valid genus of basal coelurosaurian of unknown affinities. An SVP 2016 abstract considers Tugulusaurus an alvarezsaur based on unpublished cladistic analysis of two unnamed Early Cretaceous alvarezsaurians from Xinjiang and Inner Mongolia.