In 1948, a Soviet-Mongolian expedition found the remains of a small theropod in the Gobi Desert near Nemegt. In 1987 the find was reported by Sergei Kurzanov and later that year discussed by Halszka Osmólska who suggested it could represent a specimen of the troodontid Borogovia.
Later Osmólska understood it was a species new to science. It was formalized by Kurzanov and Osmólska in 1991 as Tochisaurus nemegtensis. The generic name is derived from Mongolian toch', "ostrich", in reference to the fact that the foot, like with that bird, is functionally didactyl, i.e. has only two weight-bearing toes. The specific name refers to the Nemegt.
Its holotype fossil, PIN 551-224, was found in a layer of the Nemegt Formation, dating from the early Maastrichtian, about 69 million years old. It consists solely of the (left) metatarsus, the first discovered of an Asian troodontid. The first metatarsal is missing. The top of the fossil shows some damage that was originally somewhat inexpertly restored.
Tochisaurus is a bipedal dinosaur. The metatarsus has a length of 242 millimetres, showing it was a relatively large troodontid. The second metatarsal, 222 millimetres long, is very reduced and narrow. The joint surface on top of the metatarsus is sloped forward and downward.
Kurzanov and Osmólska, 1991