Two Gram-negative, motile and strictly aerobic marine bacteria were isolated from a tidal flat sediment sample obtained from Dae-Chun, Chung-Nam, Korea. They were preliminarily identified as Pseudoalteromonas-like bacteria, based on 16S rRNA gene sequence analysis showing nearly identical sequences (>99.7 % sequence similarity) and the highest similarity (98.4 %) to the species Pseudoalteromonas undina. Some phenotypic features of the newly isolated strains were similar to those of members of the genus Pseudoalteromonas, but several physiological and chemo-taxonomical properties readily distinguished the new isolates from previously described species. DNA-DNA hybridization with type strains of phylogenetically closely related species demonstrated that the isolates represent a novel Pseudoalteromonas species, for which the name Pseudoalteromonas marina sp. nov. is proposed, with the type strain mano4(T) (=KCTC 12242(T)=DSM 17587(T)). In addition, on the basis of this study and polyphasic data obtained from previous work, it is proposed that the species Pseudoalteromonas sagamiensis should be reclassified as Algicola sagamiensis comb. nov. and that strain B-10-31(T) (=DSM 14643(T)=JCM 11461(T)) be designated the type strain.