Two Gram-variable, rod-shaped, endospore-forming bacterial strains, which are motile with peritrichous flagella, were isolated from a Korean traditional fermented seafood, jeotgal. The two isolates (strains YKJ-1OT and YKJ-11) were proven to be members of the same species on the basis of the results of phenotypic and phylogenetic analyses and DNA relatedness. Strains YKJ-10T and YKJ-11 were characterized by having cell wall peptidoglycan based on meso-diaminopimelic acid, MK-7 as the predominant menaquinone, and iso-C15:0 as the major fatty acid. The G+C content of the DNA was 41 mol%. Strains YKJ-10T and YKJ-11 showed only a 1 bp sequence difference in the 16S rDNA sequences. The two strains formed distinct phylogenetic lineages within the radiation of the cluster comprising Bacillus species. Levels of 16S rDNA similarity between strains YKJ-10T and YKJ-11 and Bacillus species were less than 96.6%. Levels of DNA-DNA relatedness were found to be low enough to distinguish strains YKJ-10T and YKJ-11 from some phylogenetically related Bacillus species. On the basis of phenotypic properties, phylogeny and genomic distinctiveness, strains YKJ-10T and YKJ-11 represent a new species of the genus Bacillus, for which a new name, Bacillusjeotgali sp. nov., is proposed. The type strain of the new species is strain YKJ-10T (= KCCM 41040T = JCM 10885T).