A Gram-negative, coccoid or oval-shaped and gliding bacterial strain, designated HDM-25(T), belonging to the Alphaproteobacteria, was isolated from a tidal flat sediment of the Yellow Sea, Korea, and was subjected to a polyphasic taxonomic study. Strain HDM-25(T) grew optimally at pH 7.0-8.0, at 30 �XC and in the presence of 2-3% (w/v) NaCl. Neighbour-joining, maximum-likelihood and maximum-parsimony phylogenetic trees based on 16S rRNA gene sequences showed that strain HDM-25(T) fell within the clade comprising the species of the genus Paracoccus, clustering with the type strain of Paracoccus aminophilus, with which it exhibited the highest 16S rRNA gene sequence similarity (97.7%). The 16S rRNA gene sequence similarity between strain HDM-25(T) and the type strains of the other species of Paracoccus was 93.6-97.0%. The DNA G+C content was 65.9 mol% and the mean DNA-DNA relatedness between strain HDM-25(T) and the type strain of P. aminophilus was 10.7��2.7% (9.9��4.0%, reciprocal analysis). Strain HDM-25(T) contained Q-10 as the predominant ubiquinone and summed feature 8 (C(18 : 1)�s7c and/or C(18 : 1)�s6c) and C(16 : 0) as the major fatty acids. The major polar lipids were phosphatidylcholine, phosphatidylglycerol, diphosphatidylglycerol, an unidentified aminolipid, an unidentified glycolipid and an unidentified lipid. Differential phenotypic properties, together with the phylogenetic and genetic distinctiveness, demonstrated that strain HDM-25(T) is distinguishable from other species of the genus Paracoccus. On the basis of the data presented, strain HDM-25(T) is considered to represent a novel species of the genus Paracoccus, for which the name Paracoccus lutimaris sp. nov. is proposed. The type strain is HDM-25(T) (= KCTC 42007(T) = CECT 8525(T)).