Two extremely halophilic archaeal strains, designated SB29T and SB3T, were isolated from the brine-seawater interface of Discovery Deep in the Red Sea. Cells of both strains were pleomorphic (irregular polyhedrals, ovals, and rods) and stained Gram-negative; colonies were pigmented pink. The sequence similarity of the 16S rRNA gene of strain SB29T with that of its most closely related validly described species (Hfx. sulfurifontis DSM 16227T) and that of strain SB3T with its closest validly described relative (Hfx. denitrificans ATCC 35960T) was 98.1% and 98.6%, respectively. The incomplete draft genomes of SB29T and SB3T are 3,871,125 bp and 3,904,985 bp in size, respectively, and their DNA G + C contents are 60.75% and 65.64%, respectively. The highest ANI values between the genomes of SB29T and SB3T and the most closely related genomes in GenBank were determined as 82.6% (Hfx. sulfurifontis ATCC BAA-897T, GenBank accession no. GCA_000337835.1) and 92.6% (Haloferax denitrificans ATCC 35960T, GenBank accession no. GCA_000337795.1), respectively. These data indicate that the two new isolates cannot be classified into any recognized species of the genus Haloferax, and, therefore, two novel species of the genus Haloferax are proposed: Haloferax profundi sp. nov. (type strain SB29T = JCM 19567T = CGMCC 1.14960T) and Haloferax marisrubri sp. nov. (type strain SB3T = JCM 19566T = CGMCC 1.14958T).