The anthozoan sub-class Octocorallia includes over 3500 nominal species of soft corals and gorgonian sea fans, many of which serve as critical foundation species in benthic marine ecosystems in shallow waters to the deep sea. Despite their familarity and ecological importance, the diversity and taxonomy of octocorals remain poorly known. All of the orders, subordinal groups and a majority of families have been recognized to be poly- or paraphyletic, but poor resolution of the deeper nodes in mitochondrial or single-locus nuclear gene trees have hindered formal revision of the higher level taxonomy of the group. We used sequence data from target-capture of 739 ultraconserved and exon loci to reconstruct a fully resolved phylogeny for 185 octocoral taxa representing 55 of 63 currently recognized families. We use this phylogeny, supplemented with a gene tree for mitochondrial mtMutS for an additional 107 taxa, to guide a revision of the families and orders of Octocorallia. We: (1) elevate the anthozoan sub-classes Octocorallia and Hexacorallia to the rank of Class; (2) replace the three currently recognized orders of Octocorallia (Alcyonacea, Pennatulacea, Helioporacea) with two new orders reflecting reciprocally monophyletic major clades; and (3) revise all families with the exception of the 15 recognized families of sea pens, which we accommodate within a new superfamily. The revised classification of Octocorallia thus comprises 79 families, including 18 that are newly described and three that have been reinstated or elevated in rank. In addition, two new genera are described and another three reinstated. We leave the family assignment of 46 of 411 genera as incertae sedis until further molecular or morphological data can be obtained to confirm their phylogenetic affinities.