Holaxonian octocorals are diverse and abundant on many marine hard substrates and, within this group, members of the Plexauridae are an important component of tropical reef assemblages. In the most recent morphological revision of octocorals, Bayer (1981) included the Paramuriceidae (as Stenogorgiinae) within the plexaurids based on a lack of distinguishing characters. As a result, the Plexauridae now comprises 31 genera and occurs throughout the tropics as well as at higher latitudes to depths of at least 900 m. To begin to understand historical relationships within this now large and diverse assemblage, and to test the monophyly of the family and some of its component genera, DNA sequences of two mitochondrial loci (msh1 and ND2, ~1212 bp) from 40 species in 21 genera from deep and shallow waters in the tropical western Atlantic, West and East Pacific (plus 5 taxa in the closely related Gorgoniidae and two outgroups) were analyzed. Results recover three strongly supported clades that correspond roughly to the Plexauridae, Paramuriceidae and Gorgoniidae, though their mutual relationships remain unclear. Representatives of several genera appear to be scattered among the 3 "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. Some Atlantic and Pacific species of several plexaurid and paramuriceid genera were monophyletic (Muricea spp., Bebryce spp.), while others were not (Echinomuricea spp., Thesea spp., Villogorgia spp.). These molecular results indicate that current octocoral taxonomy needs revision.