Scleractinian reef corals have recently been acknowledged as the most numerous host group found in association with hydroids belonging to the Zanclea genus. However, knowledge of the molecular phylogenetic relationships among Zanclea species associated with scleractinians is just beginning. This study, using the nuclear 28S rDNA region and the fast-evolving mitochondrial 16S rRNA and COI genes, provides the most comprehensive phylogenetic reconstruction of the genus Zanclea with a particular focus on the genetic diversity among Zanclea specimens associated with 13 scleractinian genera. The monophyly of Zanclea associated with scleractinians was strongly supported in all nuclear and mitochondrial phylogenetic reconstructions. Furthermore, a combined mitochondrial 16S and COI phylogenetic tree revealed a multitude of hidden molecular lineages within this group (Clades I, II, III, V, VI, VII, and VIII), suggesting the existence of both host-generalist and genus-specific lineages of Zanclea associated with scleractinians. In addition to Z. gallii living in association with the genus Acropora, we discovered four well-supported lineages (Clades I, II, III, and VII), each one forming a strict association with a single scleractinian genus, including sequences of Zanclea associated with Montipora from two geographically separated areas (Maldives and Taiwan). Two host-generalist Zanclea lineages were also observed, and one of them was formed by Zanclea specimens symbiotic with seven scleractinian genera (Clade VIII). We also found that the COI gene allows the recognition of separated hidden lineages in agreement with the commonly recommended mitochondrial 16S as a DNA barcoding gene for Hydrozoa and shows reasonable potential for phylogenetic and evolutionary analyses in the genus Zanclea. Finally, as no DNA sequences are available for the majority of the nominal Zanclea species known, we note that they will be necessary to elucidate the diversity of the Zanclea-scleractinian association.