A total of 11 strains of moderately halophilic histamine-producing bacteria isolated from fermented squid liver sauce were studied phenotypically, genotypically, and phylogenetically. These strains are considered members of the genus Tetragenococcus based on their physiological, morphological, and chemotaxonomic characteristics. A 16S rRNA gene sequence analysis showed that these strains clustered with, but were separate from, Tetragenococcus halophilus. The results of DNA-DNA hybridization experiments indicated that the new isolates represent a new Tetragenococcus species, for which we propose the name Tetragenococcus muriaticus; strain X-1 (= JCM 10006) is the type strain of this species.