Two new reef coral species, Porites farasani sp. nov. and Porites hadramauti sp. nov. (Scleractinia, Poritidae), are described from the Red Sea and the Gulf of Aden. Porites farasani sp. nov. only occurs in the Farasan Islands in the southern Red Sea, while P. hadramauti sp. nov. has been collected in the Yemen Hadramaut region in the Gulf of Aden. Both species presented striking in situ differences with respect to other Porites species, and were characterized by small encrusting colonies and unusual polyp colouration. In order to test the genetic distinctiveness of P. farasani sp. nov. and P. hadramauti sp. nov. between each other and with respect to other representatives in the genus Porites, we investigated their evolutionary relationships with eight other morphological species of Porites occurring in the Red Sea and in the Gulf of Aden. Two DNA loci, the mitochondrial putative control region and the nuclear ribosomal ITS region, were sequenced, and three species delimitation approaches based on barcoding threshold (Automated Barcoding Gap Discovery) and coalescence theory (Poisson-Tree process, Generalized Mixed Yule Coalescent) were applied. Phylogenetic and species delimitation analyses were overall concordant, resolving P. farasani sp. nov. and P. hadramauti sp. nov. as two divergent but closely related lineages. Of the other morphologically defined Porites species, three were genetically differentiated (P. rus, P. columnaris and P. fontanesii), but five were genetically indistinguishable. The discovery of two regional endemics confirms the importance of the Red Sea and the Gulf of Aden as regions of high biodiversity and suggests the need for an integration of genome-wide molecular data with the re-evaluation of skeletal structures in the systematics of Porites.