Three Gram-negative, motile, mesophilic, aerobic, rod-shaped bacterial strains, designated 2O1(T), 1O14 and 1O18, were isolated from Indonesian seawater after enrichment with crude oil and a continuous supply of supplemented seawater. The strains exhibited high n-alkane-degrading activity, which indicated that the strains were important degraders of petroleum aliphatic hydrocarbons in tropical marine environments. Phylogenetic analyses based on 16S rRNA gene sequences of members of the Gammaproteobacteria showed that the isolates formed a coherent and distinct cluster in a stable lineage containing Oceanobacter kriegii IFO 15467(T) (96.4-96.5 % 16S rRNA gene sequence similarity) and Thalassolituus oleivorans MIL-1(T). DNA G +C content was 53.0-53.1 mol%. The major fatty acids were C(16 : 0), C(16 : 1)ω7 and C(18 : 1)ω9 and the hydroxy fatty acids were C(12 : 0) 3-OH and C(10 : 0) 3-OH. The polar lipids were phosphatidylglycerol, a ninhydrin-positive phospholipid(s) and glycolipids. The major quinone was Q-9 (97-99 %), which distinguished the isolates from Oceanobacter kriegii NBRC 15467(T) (Q-8; 91 %). On the basis of phenotypic, genotypic and chemotaxonomic data, including DNA-DNA hybridization, the isolates represent a novel genus and species, for which the name Oleibacter marinus gen. nov., sp. nov. is proposed. The type strain of Oleibacter marinus is 2O1(T) (=NBRC 105760(T) =BTCC B-675(T)).