Two Gram-negative, non-spore-forming, slightly halophilic strains, SW-135T and SW-161T, which were isolated from a tidal flat of the Yellow Sea in Korea, were subjected to a polyphasic taxonomic study. The two isolates lacked bacteriochlorophyll a and contained ubiquinone-10 (Q-10) as the predominant respiratory lipoquinone and C(18 : 1)omega7c and C(17 : 1)omega6c as the major fatty acids. The DNA G+C contents of strains SW-135T and SW-161T were 62.2 and 64.5 mol%, respectively. Phylogenetic analyses based on 16S rRNA gene sequences showed that the two strains fall within the radiation of the cluster comprising Erythrobacter species. Strains SW-135T and SW-161T exhibited a 16S rRNA gene sequence similarity value of 96.9 % and a mean DNA-DNA relatedness level of 12.3 %. Sequence similarities between strains SW-135T and SW-161T and the type strains of recognized Erythrobacter species ranged from 96.7 to 98.5 %. Levels of DNA-DNA relatedness were low enough to indicate that strains SW-135T and SW-161T represent members of two species separate from all recognized Erythrobacter species. On the basis of polyphasic taxonomic data, strains SW-135T (=KCTC 12228T=DSM 16221T) and SW-161T (=KCTC 12227T=DSM 16225T) were classified as two novel Erythrobacter species, for which the names Erythrobacter seohaensis sp. nov. and Erythrobacter gaetbuli sp. nov. are proposed, respectively.