An extremely halophilic archaeon was isolated from a sample of the brine–sediment interface of the Shaban Deep in the northern Red Sea. Phylogenetic analysis of the 16S rRNA gene sequence revealed a close proximity to Halorhabdus utahensis (99.3 %), the sole species of the genus Halorhabdus. Strain SARL4BT formed non-pigmented colonies and showed optimum growth at 45 °C, in 27 % (w/v) NaCl and at pH 6.5–7.0. This organism utilized a few complex substrates, such as yeast extract and starch, for growth. Strain SARL4BT grew under anaerobic and microaerophilic conditions but grew extremely poorly under aerobic conditions. The ether lipids were diphytanyl derivatives. The DNA G+C content of the type strain was 61.7 mol%. On the basis of the phylogenetic data and physiological and biochemical characteristics, strain SARL4BT represents a novel species of the genus Halorhabdus, for which the name Halorhabdus tiamatea is proposed. The type strain is SARL4BT (=DSM 18392T=JCM 14471T). An emended description of the genus Halorhabdus is also proposed.