El Astrodon era un gran herbívoro. Sus primeros restos se hallaron en Maryland, EE.UU., en la decáda de 1850, y después se hallaron otros en Texas. Ahora se sabe que las dos especies del género Pleurocoelus, Pleurocoelus nanus y Pleuroceolus altus, era en realidad del género Astrodon. El Astrodon tenía un largo cuello, como el de las jirafas y su cabeza era muy pequeña y tenía las fosas nasales muy elevadas.
A finales de noviembre de 1858, el químico Philip Thomas Tyson de John D. Latchford recibió dos dientes de dinosaurio. Los habían encontrado en el pozo abierto de mineral de hierro de Latchford en la Formación Arundel en Swampoodle cerca de Muirkirk en el Condado de Prince George, Maryland. Tyson dejó que fueran estudiados por el dentista Christopher Johnston, profesor de la Facultad de Odontología de Baltimore, que cortó un diente por la mitad y descubrió una sección transversal característica en forma de estrella. Johnston nombró a Astrodon en 1859. Sin embargo, no adjuntó un epíteto específico, por lo que a Joseph Leidy se le atribuye el nombre de Astrodon johnstoni (la especie tipo) en 1865, con el espécimen holotipo YPM 798. Si Johnston hubiera adjuntado un epíteto específico, sería han sido las segundas especies de dinosaurios identificadas en los Estados Unidos. Johnston declaró incorrectamente que el sitio del descubrimiento había sido una mina de hierro cerca de la ciudad de Bladensburg.
Se cree que también vivió en Europa, se sabe que eran atacados por los Utahraptor y Acrocanthosaurus porque ambos animales convivieron. Este animal era muy parecido al Sauroposeidon, de hecho, vivieron en el mismo tiempo, así que es posible que el Astrodon se una especie más pequeña del Sauroposeidon.
La Formación Arundel de Maryland data de palinomorfos hasta la etapa albiana del período Cretácico Temprano, hace unos 112 millones de años. Esta formación es parte del Grupo Potomac que incluye formaciones no solo en Maryland sino también en partes de Washington D. C., Delaware y Virginia. La Formación Arundel se depositó en el borde de la cuenca en expansión del Océano Atlántico. La región preservada en esta formación era una llanura amplia y generalmente plana con varias corrientes que la atraviesan, probablemente similar a las regiones costeras modernas de Alabama, Georgia, Louisiana y Mississippi.