The Red Sea was one of the first areas of the Indo-Pacific to be investigated by marine taxonomists, and the literature on suborder Brachycnemina (Anthozoa: Hexacorallia: Zoantharia) for this region dates from the early nineteenth century. However, in the last 100 years there has been only one focused study on this group in the Red Sea. In the present study, specimens collected from the Saudi Arabian coast of the northern half of the Red Sea were phylogenetically analyzed by sequencing nuclear internal transcribed spacer regions of ribosomal DNA (ITS-rDNA), mitochondrial cytochrome oxidase subunit I (COI), and 16S ribosomal DNA (16S–rDNA). The new results were compared with historical data in the literature and recent results from the Persian Gulf and the southeastern coast of Africa. Results show the presence of six to seven potential Brachycnemina species in the Red Sea; five to six Palythoa species (Palythoa mutuki, P. tuberculosa, P. cf. heliodiscus, P. aff. heliodiscus, and one to two species within the P. sp. “sakurajimensis” group) together with Zoanthus sansibaricus. While P. mutuki, P. tuberculosa, and Z. sansibaricus are known to be widely distributed in the Indo-Pacific, P. cf. heliodiscus and P. sp. “sakurajimensis” have not been reported from the Persian Gulf or the southeastern coast of Africa, and the current results represent large range extensions for these two species. Only one of the observed species, P. aff. heliodiscus, is potentially endemic to the Red Sea, further demonstrating the generally wide distributions of most zooxanthellate Brachycnemina species.