Octocorals are diverse and abundant on many marine hard substrates, and, within this group, members of the family Plexauridae are an important component of tropical reef assemblages, especially in the Caribbean. To understand historical relationships within this large and diverse assemblage, and to test the monophyly of the family and some of its genera, DNA sequences of two mitochondrial loci (msh1 and ND2, ~1,185 bp) were analyzed from 46 species in 21 genera from deep and shallow waters in the tropical western Atlantic and in the tropical western and eastern Pacific (plus 9 taxa in the closely related Gorgoniidae and 1 species of the more distantly related Alcyoniidae). Five strongly supported clades were recovered. Three large clades correspond roughly to the Plexauridae, Paramuriceidae, and Gorgoniidae, and two smaller clades were comprised of taxa previously assigned to several families. Astrogorgia sp. did not group with any of the clades. The mutual relationships among the five clades remain unclear. Several genera previously regarded as unrelated appear to be grouped among the three “families”; e.g. Hypnogorgia sp. (Paramuriceidae) falls within a clade consisting of both Pacific and Atlantic Muricea spp. (Plexauridae), while Swiftia sp., Scleracis sp., and an Atlantic Thesea sp. (all Paramuriceidae) group with the gorgoniids. In several instances, genera containing Atlantic and Pacific species were recovered as monophyletic (Muricea spp., Bebryce spp.). However, in at least three cases (Echinomuricea spp., Thesea spp.,Villogorgia spp.), placement of Atlantic and Pacific species in the same genus may reflect convergence of sclerite morphology. The results indicate a strong need for reexamination of octocoral taxonomy using a combination of molecular, morphological, and chemical evidence.