Relationships between the major lineages of snakes are assessed based on a phylogenetic analysis of the most extensive phenotypic data set to date (212 osteological, 48 soft anatomical, and three ecological characters). The marine, limbed Cretaceous snakes Pachyrhachis and Haasiophis emerge as the most primitive snakes: characters proposed to unite them with advanced snakes (macrostomatans) are based on unlikely interpretations of contentious elements or are highly variable within snakes. Other basal snakes include madtsoiids and Dinilysia – both large, presumably non-burrowing forms. The inferred relationships within extant snakes are broadly similar to currently accepted views, with scolecophidians (blindsnakes) being the most basal living forms, followed by anilioids (pipesnakes), booids and booid-like groups, acrochordids (filesnakes), and finally colubroids. Important new conclusions include strong support for the monophyly of large constricting snakes (erycines, boines, pythonines), and moderate support for the non-monophyly of the ‘trophidophiids’ (dwarf boas). These phylogenetic results are obtained whether varanoid lizards, or amphisbaenians and dibamids, are assumed to be the nearest relatives (outgroups) of snakes, and whether multistate characters are treated as ordered or unordered. Identification of large marine forms, and large surface-active terrestrial forms, as the most primitive snakes contradicts with the widespread view that snakes arose via minute, burrowing ancestors. Furthermore, these basal fossil snakes all have long flexible jaw elements adapted for ingesting large prey (‘macrostomy’), suggesting that large gape was primitive for snakes and secondarily reduced in the most basal living foms (scolecophidians and anilioids) in connection with burrowing. This challenges the widespread view that snake evolution has involved progressive, directional elaboration of the jaw apparatus to feed on larger prey.