New anatomical observations and reinterpretations of previously identified structures have resulted in new taxonomic diagnoses for the fossil hind-limbed marine snakes Pachyrhachis problematicus, Eupodophis descouensi, and Haasiophis terrasanctus. Among the most important conclusions of our study are the following: Haasiophis and Eupodophis show no evidence of possessing a laterosphenoid; Pachyrhachis and Eupodophis do retain a jugal; Haasiophis, like Eupodophis, has chevron bones in the caudal region; Haasiophis has a large number of unfused intercentra along the anterior portion of the precloacal column; the dentary of Pachyrhachis has numerous mental foramina (at least four); Pachyrhachis has at least one sacral vertebra with unfused sacral ribs. To test the effect of our new observations on the phylogenetic relationships of snakes, we ran three phylogenetic analyses using alternative outgroups to polarize the character transformations. The ingroup consisted of all well-preserved fossil snakes from the Cretaceous, the madtsoiids, and taxa that are representative of all major groups of extant snakes. The analyses yielded a series of most parsimonious trees that placed Pachyrhachis, Eupodophis, and Haasiophis either as a series of stem taxa at the base of the radiation of snakes (two analysis), or as members of a clade of fossil snakes that are the sister group of all living alethinopidians (one analysis).