Holothuroids, or sea cucumbers, are an abundant and diverse group of echinoderms with over 1400 species occurring from the intertidal to the deepest oceanic trenches. In this study, we report the first phylogeny of this class, based on a cladistic analysis of 47 morphological characters. We introduce several previously unconsidered synapomorphic characters, examine the relationships between representatives from all extant families and assess the assumptions of monophyly for each order and subclass. Maximum-parsimony analyses using three rooting methods recovered well-supported and identical topologies when two small and apparently derived families, Eupyrgidae and Ge-phyrothuriidae, were removed. The results suggest that the higher-level arrangement of Holothuroidea warrants a considerable revision. Apodida was sister to the other holothuroids. The monophyly of Dendrochirotida was not supported and the group may be paraphyletic. A randomization test using Wills’ gap excess ratio found significant congruence between the phylogeny and the stratigraphic record of fossil members, suggesting that the fossil record of holothuroids is not as incomplete as is often stated. The fossil-calibrated tree indicated that several groups of holothuroids survived the end-Permian mass extinction and that the clade composed of Dendrochirotida, Dactylochirotida, Aspidochirotida and Molpadiida rapidly radiated during the Triassic.