Two novel rod-shaped, Gram-stain-negative, aerobic and non-motile bacterial strains, designated M39(T) and C2-7(T), were isolated from the coastal sediment of Xiaoshi Island, Weihai, PR China. Growth of strain M39(T) occurred at 15-37 degrees C, at pH 6.0-9.0 and in the presence of 1.0-9.0 % (w/v) NaCl. Strain C2-7(T) grew at 15-40 degrees C, at pH 6.0-8.0 and in the presence of 0.5-8.0 % (w/v) NaCl. Phylogenetic analysis based 16S rRNA gene sequences revealed that strains M39(T) and C2-7(T) belong to the phylum Bacteroidota. Based on the results of 16S rRNA gene sequence analysis, the closest relative of strain M39(T) was Robiginitalea marina KCTC 92035T (95.4%), and the closest relative of strain C2-7(T) was Algoriphagus namhaensis DPG-3(T) (97.0%). The percentage of conserved protein and average nucleotide identity values between strain M39(T) and some species of the genus Robiginitalea were 66.9-77.6% and 69.3-71.0%, respectively, while those between strain C2-7(T) and some species of the genus Algoriphagus were 68.0-70.1% and 56.1-72.6 %, respectively. The major cellular fatty acids (>10%) of strain M39(T) consisted of iso-C-15:1 F, iso-C-15:0 and iso-C-17:0 3-OH, while those of strain C2-7(T) were iso-C-15:0 and C-16:1 omega 7c/C-16:1 omega 6c. MK-6 was the only respiratory quinone that was compatible with the genus of strain M39(T). The predominant menaquinone of strain C2-7(T) was MK-7. The major polar lipids of strain M39(T) were phosphatidylethanolamine and glycolipids, and those of strain C2-7(T) were phosphatidylethanolamine, one unidentified aminolipid and four unidentified lipids. The DNA G+C contents of strains M39T and C2-7(T) were 46.9 and 40.8mol%, respectively. Based upon the results presented in this study, strains M39(T) and C2-7(T) represent novel species of the genera Robiginitalea and Algoriphagus, respectively, for which the names Robiginitalea aurantiaca sp. nov. and Algoriphagus sediminis sp. nov. are proposed with the type strains M39(T) (=MCCC 1H00498(T)=KCTC 92014(T)) and C2-7(T) (=MCCC 1H00414(T)=KCTC 92027(T)).