These vertebrae were discovered in May 1994 at the Antlers Formation in Atoka County, Oklahoma by dog trainer Bobby Cross and secured by Dr. Richard Cifelli and a team from the Oklahoma Museum of Natural History in May 1994 and August 1994. Initially the fossils were believed to be simply too large to be the remains of an animal, and due to the state of preservation, believed to be tree trunks. In fact, they are the longest such bones known in dinosaurs. Thus, the vertebrae were stored until 1999, when Dr. Cifelli gave them to a graduate student, Matt Wedel, to analyze as part of a project. Upon their realization of the find's significance, they issued a press release in October 1999, followed by official publication of their findings in the "Journal of Vertebrate Paleontology" in March 2000. The new species was named "S. proteles", and the holotype is OMNH 53062. The generic name comes from "sauros" (Greek σαύρος for "lizard"), and "Poseidon" (Ποσειδών), the sea god in Greek mythology, who is also associated with earthquakes, that facet styled as Ennosigaios or Enosikhthōn, "Earthshaker". This is a reference to the notion that a sauropod's weight was so great that the ground shook as it walked. The specific descriptor "proteles" also comes from the Ancient Greek πρωτέλης and means "perfect before the end", which refers to "Sauroposeidon's" status as the last and most specialized giant sauropod known in North America, during the Early Cretaceous. In 2012, numerous other sauropod remains that had been known for decades under various different names were also classified in the genus "Sauroposeidon". Sauropod bones and trackways had long been known from the Paluxy River area of Texas, usually referred to the genus "Pleurocoelus", including partial skeletons (particularly from the Glen Rose Formation, above the Twin Mountains Formation). In the mid 1980s, students from the University of Texas at Austin discovered a bonebed on a ranch in Hood County, but early work stopped in 1987. The quarry was reopened in 1993 and was subsequently worked by parties from Southern Methodist University, the Fort Worth Museum of Science and History, and Tarleton State University.