Polychelidan lobsters are unique decapod crustaceans characterized by having four or five pairs of claws. We still do not have a clear overview of the 69 described species of fossil polychelidans and, until now, little was known of their phylogenetic relationships. Our phylogenetic analysis includes 35 fossil polychelidans and offers the first high-resolution study of their relationships, uniting fossil and extant polychelidans. It shows that polychelidans are divided into five main lineages - two monospecific (Palaeopentacheles roettenbacheri and Rogeryon oppeli) and three clades (Eryonidae, Coleiidae and Polychelidae). The recent inclusion of Tetrachelidae within Coleiidae is confirmed. The analysis allowed the identification of diagnostic characters for Eryonidae and demonstrates that Eryon siburicus from the Toarcian is the oldest occurrence of this family. The diverse Coleia is polyphyletic. We were able to identify several trends in polychelidan evolution: (1) diversification of the main lineages probably predates the Late Triassic; (2) Eryonidae probably evolved fossorial adaptations independently; (3) the general trend to live in deeper water disappears when accounting for the bathyal distribution of each monophyletic group across time; (4) several lineages conquered shallowwater palaeoenvironments; and (5) fossil polychelids inhabited deep water as early as the Early-Middle Jurassic. Extant polychelidans are not refugees that adapted to deep water, but survivors of a group that was once more diverse both morphologically and ecologically.