Sea cucumbers (Holothuroidea) are a morphologically diverse, ecologically important, and economically valued clade of echinoderms; however, the understanding of the overall systematics of the group remains controversial. Here, we present a phylogeny of extant Holothuroidea assessed with maximum parsimony, maximum likelihood, and Bayesian approaches using approximately 4.3kb of mt- (COI, 16S, 12S) and nDNA (H3, 18S, 28S) sequences from 82 holothuroid terminals representing 23 of the 27 widely-accepted family-ranked taxa. Currently five holothuroid taxa of ordinal rank are accepted. We find that three of the five orders are non-monophyletic, and we revise the taxonomy of the groups accordingly. Apodida is sister to the rest of Holothuroidea, here considered Actinopoda. Within Actinopoda, Elasipodida in part is sister to the remaining Actinopoda. This latter clade, comprising holothuroids with respiratory trees, is now called Pneumonophora. The traditional Aspidochirotida is paraphyletic, with representatives from three orders (Molpadida, Dendrochirotida, and Elasipodida in part) nested within. Therefore, we discontinue the use of Aspidochirotida and instead erect Holothuriida as the sister group to the remaining Pneumonophora, here termed Neoholothuriida. We found four well-supported major clades in Neoholothuriida: Dendrochirotida, Molpadida and two new clades, Synallactida and Persiculida. The mapping of traditionally-used morphological characters in holothuroid systematics onto the phylogeny revealed marked homoplasy in most characters demonstrating that further taxonomic revision of Holothuroidea is required. Two time-tree analyses, one based on calibrations for uncontroversial crown group dates for Eleutherozoa, Echinozoa and Holothuroidea and another using these calibrations plus four more from within Holothuroidea, showed major discrepancies, suggesting that fossils of Holothuroidea may need reassessment in terms of placing these forms with existing crown clades.