The type species, E. yahnahpin, was described by James Filla and Patrick Redman in 1994 as a species of Apatosaurus (A. yahnahpin). The specific name is derived from Lakota mah-koo yah-nah-pin, "breast necklace", a reference to the pairs of sternal ribs that resemble the hair pipes traditionally worn by the tribe. The holotype is TATE-001, a relatively complete postcranial skeleton found in Wyoming, in the lower Morrison Formation. More fragmentary remains have also been referred to the species.
A re-evaluation by Robert T. Bakker in 1998 found it to be more primitive, and so Bakker coined the new generic name Eobrontosaurus, derived from Greek eos, "dawn", and Brontosaurus, the original generic name of Apatosaurus excelsus. It has been argued that Eobrontosaurus yahnahpin actually belongs within Camarasaurus, although this has been questioned. According to Bakker Eobrontosaurus was a member of the Diplodocidae, more specifically the Apatosaurinae.