Two marine, Gram-negative, aerobic, halophilic strains, designated KMM 3657T and KMM 3840T, were isolated and found to be phylogenetically closely related to each other, showing 96.6 % 16S rRNA gene sequence similarity. Both strains are members of the genus Marinobacter in the gamma-Proteobacteria (94.7-98.0 % 16S rRNA gene sequence similarity). Strain KMM 3657T and Marinobacter lipolyticus SM19T were closely related, with 98.0 % sequence similarity. The novel strains shared generic physiological and chemotaxonomic properties with Marinobacter species, but differed in their temperature range for growth, inability to grow in 20 % NaCl and at >43 degrees C, metabolic properties and fatty acid composition. On the basis of phenotypic and phylogenetic analysis data, it is proposed that the strains represent two novel species, Marinobacter bryozoorum sp. nov., with the type strain KMM 3840T (=50-11T=DSM 15401T), and Marinobacter sediminum sp. nov., with the type strain KMM 3657T (=R65T=DSM 15400T).