Two Gram-negative, motile, aerobic bacterial strains, designated B2(T) and 1_C16_27(T), were respectively isolated from a seawater sample collected from the East China Sea and a semi-coke sample from north-eastern Estonia. Their genetic, phenotypic and chemotaxonomic properties were studied. The isolates were short rods with polar flagella and were positive for catalase and oxidase activities. Q-10 was the predominant respiratory ubiquinone. The major polar lipids were phosphatidylglycerol, diphosphatidylglycerol and two unidentified glycolipids. The major fatty acids were nonadecanoic (C(19 : 0) cyclo), octadecanoic (C(18 : 0) and C(18 : 0) 3-OH), octadecenoic (C(18 : 1)) and hexadecanoic (C(16 : 0)) acids. The G+C content of the genomic DNA was 58.1-59.3 mol%. 16S rRNA gene sequence analysis revealed that the two isolates represent a distinct lineage within the family Hyphomicrobiaceae. The phylogenetically closest relatives were Cucumibacter (92.7-93.7 % 16S rRNA gene sequence similarity), Devosia (92.9-94.4 %) and Zhangella (91.7-92.1 %). Differential phenotypic properties, together with phylogenetic and genetic distinctiveness, revealed that strains B2(T) and 1_C16_27(T) could be differentiated from each other and from members of the genera Cucumibacter, Devosia and Zhangella. Therefore, it is proposed that strains B2(T) and 1_C16_27(T) represent two novel species in a new genus, for which the names Pelagibacterium halotolerans gen. nov., sp. nov. (the type species; type strain B2(T) = CGMCC 1.7692(T) = JCM 15775(T)) and Pelagibacterium luteolum sp. nov. (type strain 1_C16_27(T) = CGMCC 1.10267(T) = JCM 16552(T) = CELMS EEUT 1C1627(T)) are proposed.