The widespread assumption that COI and other mitochondrial genes will be ineffective DNA barcodes for anthozoan cnidarians has not been well tested for most anthozoans other than scleractinian corals. Here we examine the limitations of mitochondrial gene barcoding in the sub-class Octocorallia, a large, diverse, and ecologically important group of anthozoans. Pairwise genetic distance values (uncorrected p) were compared for three candidate barcoding regions: the Folmer region of COI; a fragment of the octocoral-specific mitochondrial protein-coding gene, msh1; and an extended barcode of msh1 plus COI with a short, adjacent intergenic region (igr1). Intraspecific variation was <0.5%, with most species exhibiting no variation in any of the three gene regions. Interspecific divergence was also low: 18.5% of congeneric morphospecies shared identical COI barcodes, and there was no discernible barcoding gap between intra- and interspecific p values. In a case study to assess regional octocoral biodiversity, COI and msh1 barcodes each identified 70% of morphospecies. In a second case study, a nucleotide character-based analysis correctly identified 70% of species in the temperate genus Alcyonium. Although interspecific genetic distances were 2× greater for msh1 than COI, each marker identified similar numbers of species in the two case studies, and the extended COI + igr1 + msh1 barcode more effectively discriminated sister taxa in Alcyonium. Although far from perfect for species identification, a COI + igr1 + msh1 barcode nonetheless represents a valuable addition to the depauperate set of characters available for octocoral taxonomy. © 2010 Blackwell Publishing Ltd.