The first fossil remains of this dinosaur were discovered in early August 1963 by a team of Professor Zofia Kielan-Jaworowska at Tsagan Khushu during a Polish-Mongolian expedition to the Gobi Desert of Mongolia. The find was reported by her in 1965. In 1972, it was named and described by paleontologists Rinchen Barsbold, Halszka Osmólska, and Ewa Roniewicz. The only named species is the type species Gallimimus bullatus. The generic name is derived from Latin gallus, "chicken", and mimus, "mimic", in reference to the neural arches of the front neck vertebrae which resemble those of the Galliformes. The specific name is derived from Latin bulla, a magic capsule worn by Roman youth around the neck, in reference to a bulbous swelling in the braincase on the underside of the parasphenoid, in the form of a capsule.
The holotype specimen, IGM 100/11, consists of a partial skeleton including the skull and lower jaws. It is a larger skeleton; several other partial skeletons have been described, most of them of juveniles, and numerous single bones.
A second species announced by Barsbold in 1996, "Gallimimus mongoliensis" based on specimen IGM 100/14 from the older Bayanshiree Formation, has never been formally referred to this genus. In a reanalysis of the nearly complete skeleton of "Gallimimus mongoliensis" Barsbold concluded in 2006 that it is not a species of Gallimimus but may represent a new, currently unnamed ornithomimid genus.
Gallimimus was rather ostrich-like, with a small head, toothless beak, large eyes, a long neck, short arms, long legs, and a long tail. A diagnostic character of Gallimimus is a distinctly short 'hand' relative to the humerus length, when compared to other ornithomimids. The tail was used as a counterbalance. The eyes were located on the sides of its head, meaning that it did not possess binocular vision. Like most modern birds and other theropods, it had hollow bones. Gallimimus had a number of adaptations which suggest good running ability, such as a strong ilium, heavy tail base, long limbs, a long tibia and metatarsus and short toes, but it is unknown how fast it could run. All ornithomimids had long skulls but that of Gallimimus was exceptionally elongated, due to an elongation of the snout. The snouts of the juvenile specimens are much shorter.
Norwegian researcher Jørn H. Hurum in 2001 published a detailed description of a complete lower jaw bone from Gallimimus bullatus. He observed that the bones composing the jaw were "paper thin". and corrects minor mistakes made in previous reconstructions of the lower jaw of G. bullatus. He also observed that the tight intramandibular joint would prevent any movement between the front and rear portions of the lower jaw.