A Gram-stain-negative and facultatively aerobic bacterium, designated as strain CBA4604T, was isolated from a traditional Korean salted and fermented shrimp food (saeu-jeot). Phylogenetic analysis based on 16S rRNA gene sequences showed that strain CBA4604T formed a clearly distinct phyletic lineage from closely related species within the genus Paracoccus. Strain CBA4604T was the most closely related to P. koreensis Ch05T (97.5% 16S rRNA gene sequence similarity) and other type strains (≤ 97.0%). The genome comprised a chromosome and two plasmids of 3,299,166 bp with 66.5% G+C content. The DNA-DNA relatedness values between strain CBA4604T and P. koreensis Ch05T, P. alcaliphilus DSM 8512T, and P. stylophorae KTW-16T were 30.5%, 22.9%, and 16.7%, respectively. Cells of the strain were short rod-shaped and oxidase- and catalase-positive. The growth of strain CBA-4604T was observed at 10-40°C (optimum, 37°C), pH 6.0-10.0 (optimum, pH 7.0), and in the presence of 0-8.0% (w/v) NaCl (optimum, 0-2.0%). Strain CBA4604T contained ubiquinone 10 as the sole isoprenoid quinone and summed feature 8 (C18:1ω7c/C18:1ω6c) and C18:0 as the major cellular fatty acids. The polar lipids consisted of phosphatidylcholine, phosphatidylglycerol, diphosphatidylglycerol, phospholipid, an unidentified aminolipid, an unidentified glycolipid, and three unidentified lipids. Based on its phylogenetic, genomic, phenotypic, and chemotaxonomic features, we concluded that strain CBA-4604T represents a novel species in the genus Paracoccus and we propose the name Paracoccus jeotgali sp. nov. The type strain is CBA4604T (= KACC 19579T = JCM 32510T).