Mitochondrial genomes have recently become widely used in animal phylogeny, mainly to infer the relationships between vertebrates and other bilaterians. However, only 11 of 723 complete mitochondrial genomes available in the public databases are of early metazoans, including cnidarians (Anthozoa, mainly Scleractinia) and sponges. Although some cnidarians (Medusozoa) are known to possess atypical linear mitochondrial DNA, the anthozoan mitochondrial genome is circular and its organization is similar to that of other metazoans. Because the phylogenetic relationships among Anthozoa as well as their relation to other early metazoans still need to be clarified, we tested whether sequencing the complete mitochondrial genome of Savalia savaglia, an anthozoan belonging to the order Zoantharia (=Zoanthidea), could be useful to infer such relationships. Compared to other anthozoans, S. savaglia's genome is unusually long (20,766 bp) due to the presence of several noncoding intergenic regions (3691 bp). The genome contains all 13 protein coding genes commonly found in metazoans, but like other Anthozoa it lacks most of the tRNAs. Phylogenetic analyses of S. savaglia mitochondrial sequences show Zoantharia branching closely to other Hexacorallia, either as a sister group to Actiniaria or as a sister group to Actiniaria and Scleractinia. The close relationships suggested between Zoantharia and Actiniaria are reinforced by strong similarities in their gene order and the presence of similar introns in the COI and ND5 genes. Our study suggests that mitochondrial genomes can be a source of potentially valuable information on the phylogeny of Hexacorallia and may provide new insights into the evolution of early metazoans.