Two Gram-positive, non-motile, non-spore-forming, halotolerant and moderately halophilic cocci (strains YKJ-101T and YKJ-115T) were isolated from the traditional Korean fermented seafood jeotgal, and were investigated using a polyphasic taxonomic approach. Phylogenetic analysis of 16S rDNA sequences showed that strains YKJ-101T and YKJ-115T are most closely related to the cluster comprising two Salinicoccus species. The peptidoglycan type of the strains is A3alpha, based on L-Lys-Gly(3-4)-L-Ala(Gly), and the predominant menaquinone is MK-7. Strains YKJ-101T and YKJ-115T have cellular fatty acid profiles containing major amounts of saturated, unsaturated and branched fatty acids; the major fatty acids are anteiso-C15 : 0 and iso-C15 : 0. The cellular polar lipids are phosphatidylglycerol, diphosphatidylglycerol and unidentified phospholipids. Strains YKJ-101T and YKJ-115T have identical DNA G + C contents of 42 mol%. The 16S rDNA similarity between strains YKJ-101T and YKJ-115T is 98% and the mean level of DNA-DNA relatedness between the two strains is 13.4%. On the basis of phenotypic and phylogenetic data and genomic distinctiveness, it is proposed that strains YKJ-101T and YKJ-115T should be placed in a new genus, Jeotgalicoccus gen. nov., as two distinct new species, for which the names Jeotgalicoccus halotolerans sp. nov. and Jeotgalicoccus psychrophilus sp. nov. are proposed. The type strains are YKJ-101T (=KCCM 41448T =JCM 11198T) and YKJ-115T (=KCCM 41449T =JCM 11199T), respectively.