Two new reef coral species, $\textit{Porites farasani}$ sp. nov. and $\textit{Porites hadramauti}$ sp. nov. (Scleractinia, Poritidae), are described from the Red Sea and the Gulf of Aden. $\textit{Porites farasani}$ sp. nov. only occurs in the Farasan Islands in the southern Red Sea, while $\textit{P. hadramauti}$ sp. nov. has been collected in the Yemen Hadramaut region in the Gulf of Aden. Both species presented striking $\textit{in situ}$ differences with respect to other $\textit{Porites}$ species, and were characterized by small encrusting colonies and unusual polyp colouration. In order to test the genetic distinctiveness of $\textit{P. farasani}$ sp. nov. and $\textit{P. hadramauti}$ sp. nov. between each other and with respect to other representatives in the genus $\textit{Porites}$, we investigated their evolutionary relationships with eight other morphological species of $\textit{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 $\textit{P. farasani}$ sp. nov. and $\textit{P. hadramauti}$ sp. nov. as two divergent but closely related lineages. Of the other morphologically defined $\textit{Porites}$ species, three were genetically differentiated ($\textit{P. rus}$, $\textit{P. columnaris}$ and $\textit{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 $\textit{Porites}$.