In 1923, during the American Museum of Natural History expedition by Roy Chapman Andrews to Inner Mongolia, Peter Kaisen discovered numerous theropod remains in three quarries. These were named and shortly described by Charles Whitney Gilmore in 1933 as a new species of Ornithomimus: Ornithomimus asiaticus. The specific name refers to the Asian provenance. The species was placed in the new genus Archaeornithomimus by Dale Russell in 1972, making Archaeornithomimus asiaticus the type species of the genus. The generic name combines that of Ornithomimus with a Greek ἀρχαῖος (archaios), "ancient", because Russell mistakenly believed that the layers Archaeornithomimus was found in dated to the Cenomanian-Turonian, about 95 million years old, making it one of the oldest ornithomimids known at the time. Gilmore had not assigned a holotype specimen; in 1990 David Smith and Peter Galton in the first comprehensive description of the fossils, choose specimen AMNH 6565, a foot, as the lectotype.
The fossils were found in the Iren Dabasu Formation, which is seen as dating to the Campanian-Maastrichtian. They consist of the largely disarticulated remains of several individuals. Material of the skull and the lower jaws is lacking.
Foot bones found in the Early Cretaceous Arundel Formation of Maryland had been referred by Othniel Charles Marsh to Allosaurus medius. In 1911 Richard Swann Lull named these as a new species of Dryptosaurus: Dryptosaurus grandis. In 1920 Gilmore renamed them to a new species of Ornithomimus. As a Ornithomimus grandis already existed however, he coined the new species name Ornithomimus affinis. In 1972 Russell, despite the fact that the correct new combination should have been A. grandis, renamed them a second species of Archaeornithomimus: Archaeornithomimus affinis. In 1990 Smith and Galton concluded the remains were not ornithomimosaurian and came from some other small theropod.
In 1995 a third species of Archaeornithomimus was named by Lev Nesov: Archaeornithomimus bissektensis, based on holotype N 479/12457, a thighbone of a juvenile, found in the Bissekty Formation of Uzbekistan, dating to the Turonian-Coniacian. Today the affinity with Archaeornithomimus asiaticus is generally doubted.
Archaeornithomimus asiaticus was about 3.3 meters (11 ft) long, and weighed up to 50 kilograms (110 lb). The hindlimbs were robustly built. The third metatarsal was not pinched at the upper end, so the foot was not arctometatarsalian. Like other members of the ornithomimids, Archaeornithomimus was perhaps an omnivore, eating everything from small mammals, to plants and fruit, to eggs, and even hatchlings of other Asian dinosaurs.
Russell assigned Archaeornithomimus to the Ornithomimidae. Recent cladistic analyses either confirm this or recover the species outside of the Ornithomimidae, basal in the Ornithomimosauria.
In a 2001 study conducted by Bruce Rothschild and other paleontologists, 229 foot bones referred to Archaeornithomimus were examined for signs of stress fracture, but none were found.