Extant biodiversity can easily be underestimated owing to the presence of cryptic taxa, even among commonly observed species. Scleractinian corals are challenging to identify because of their ecophenotypic variation and morphological plasticity. In addition, molecular analyses have revealed the occurrence of cryptic speciation. Here, we describe a new cryptic lobophylliid genus and species Paraechinophyllia variabilis gen. nov., sp. nov., which is morphologically similar to Echinophyllia aspera and E. orpheensis. The new taxon occurs in Mayotte Island, Madagascar, the Gulf of Aden and the Red Sea. Six molecular markers (COI, 12S, ATP6-NAD4, NAD3-NAD5, histone H3 and ITS) and 46 morphological characters at three different levels (macromorphology, micromorphology and microstructure) were examined. The resulting molecular phylogenetic reconstruction showed that Paraechinophyllia gen. nov. represents a distinct group within the Lobophylliidae that diverged from the lineage leading to Echinophyllia and Oxypora in the Early Miocene, approximately 21.5 Ma. The morphological phylogenetic reconstruction clustered Paraechinophyllia gen. nov., Echinophyllia and Oxypora together in a single clade. A sole morphological character, calice relief, discriminated Paraechinophyllia gen. nov. from the latter two genera, suggesting that limited morphological variation has occurred over a long period. These results highlight the importance of cryptic taxa in reef corals, with implications for population genetics, ecological studies and conservation.