[1] The species is named in honour of Charles Hazelius Sternberg and his son, Levi, who discovered the type specimen in the Niobrara Chalk during the summer of 1918.

Autapomorphies: parietal with smooth triangular table extending very far posteriorly, bearing medium-sized circular foramen, located at distance twice its diameter from the frontal-parietal suture, and surrounded anteriorly and posteriorly by two parallel ridges; rounded quadrate with regularly convex tympanic ala (wing); vertebral formula: seven cervicals, 24 dorsals, four pygals, 28 median caudals and at least 41 terminal caudals; humerus length approximately 2.5x distal width."

E. coellensis is diagnosed by more retracted nostrils, between the 7 and the 17 maxillary teeth, premaxilla and maxilla with a short rostrum anterior to the first teeth; presence of a septomaxilla, a large prefrontal that makes most of the margin of the outer nostril, a short and wide frontal, a parietal foramen located near of the fronto-parietal suture, a triangular surface of the parietal with two medial depressions and 22 caudal vertebrae.

It have features of the mosasauroids, with three vertebrae with haemal arches and procoelic centra, that suggest the possibility that these small bones belong to an embryo of this species, although the lack of diagnostic fossils like the skull or teeth prevents a complete identification.

[8][2][9] Below is a cladogram following an analysis by Takuya Konishi and colleagues (2016) done during the description of Phosphorosaurus ponpetelegans, which showcases the internal relationships within the Halisaurinae.

They suggested that Phosphorosaurus ponpetelegans and Eonatator coellensis were more closely related to the genus Halisaurus than the type species of their respective genera.