Two moderately halophilic Gram-negative bacteria were isolated from a sample taken from the brine–seawater interface of the Shaban Deep in the Red Sea. Phylogenetic analysis of the 16S rRNA gene sequence showed that these organisms represent a novel species of the genus Marinobacter. Cells of the new isolates formed non-pigmented colonies and were motile by means of a single polar flagellum. Strains SD-14B^T and SD-14C grew optimally at 35–37 °C, in 5 % NaCl and at pH 7.5–8.0. The organisms were aerobic, but reduced nitrate to nitrogen under anaerobic conditions. Acid was produced from only a few carbohydrates. Ubiquinone 9 was the major respiratory quinone. The major fatty acids of strains SD-14B^T and SD-14C were C_{16 : 0}, C_{18 : 1} ω9c, summed feature 3 (C_{16 : 1} ω6c/C_{16 : 1} ω7c) and C_{12 : 0} 3-OH. The DNA G+C contents were 55.9 and 55.7 mol%, respectively. On the basis of the phylogenetic analyses and physiological and biochemical characteristics, it is proposed that strains SD-14B^T and SD-14C represent a novel species of the genus Marinobacter, with the name Marinobacter salsuginis sp. nov. The type strain is strain SD-14B^T (=DSM 18347^T=LMG 23697^T).