Fire corals of the hydrocoral genus Millepora provide an important ecological role as framework builders of coral reefs in the Indo-Pacific and the Atlantic. Recent works have demonstrated the incongruence between molecular data and the traditional taxonomy of Millepora spp. based on overall skeleton growth form and pores. In an attempt to establish a reliable and standardized approach for defining species boundaries in Millepora, we focused on those from the Red Sea. In this region, three species are currently recognized: the fan-shaped branching M. dichotoma, the blade-like M. platyphylla, and the massive/encrusting M. exaesa. A total of 412 colonies were collected from six localities. Two mitochondrial marker genes (COI and 16S rDNA) were sequenced to obtain phylogeny reconstructions and haplotype networks. Eight morphological traits of pores and the nematocysts of both polyp and eumedusoid stages were measured to determine whether significant morphological differences occur among the three species. Both markers clearly resolved M. dichotoma, M. platyphylla, and M. exaesa as distinct, monophyletic lineages in the Red Sea. Nevertheless, they also revealed deep genetic breaks with Southwestern Indian Ocean populations of the three species. In the Red Sea, the three species were further distinguished based on their pore and nematocyst features. A discriminant analysis revealed dactylopore density, number of dactylopores per gastropore, dactylopore distance, and gastropore diameter as the most informative discriminative characters. The heteronemes, the large and small stenoteles of polyps, and the distribution of mastigophores of eumedusoids also showed significant interspecific differences. An integrated morpho-molecular approach proved to be decisive in defining species boundaries of Millepora supported by a combination of pore and nematocyst characters, which may be phylogenetically informative.