Zoantharia (or Zoanthidea) is the third largest order of Hexacorallia, characterised by two rows of tentacles, one siphonoglyph and a colonial way of life. Current systematics of Zoantharia is based exclusively on morphology and follows the traditional division of the group into the two suborders Brachycnemina and Macrocnemina, each comprising several poorly defined genera and species. To resolve the phylogenetic relationships among Zoantharia, we have analysed the sequences of mitochondrial 16S and 12S rRNA genes obtained from 24 specimens, representing two suborders and eight genera. In view of our data, Brachycnemina appears as a monophyletic group diverging within the paraphyletic Macrocnemina. The macrocnemic genus Epizoanthus branches as the sister group to all other Zoantharia that are sampled. All examined genera are monophyletic, except Parazoanthus, which comprises several independently branching clades and individual sequences. Among Parazoanthus, some groups of species can be defined by particular insertion/deletion patterns in the DNA sequences. All these clades show specificity to a particular type of substrate such as sponges or hydrozoans. Substrate specificity is also observed in zoantharians living on gorgonians or anthipatharians, as in the genus Savalia (Gerardia). If confirmed by further studies, the substrate specificity could be used as reliable character for taxonomic identification of some Macrocnemina.