Three protease-producing halophilic bacteria were isolated from fermenting anchovy. Isolated FAM 10, FAM 114, and FAM 115 were found to grow optimally at salt concentrations of 2-4%, 10%, and 6%, respectively, and could grow in salinity of up to 18-22%. The salinity conditions for optimum protease production were 6% in FAM 10 and 10% in FAM 114 and FAM 115. The protease activity of FAM 10 was gradually inhibited by the addition of NaCl up to 10%, and was not evident at 14%, whereas FAM 114 and FAM 115 displayed protease activity at 14% NaCl and could not be measured at 18%. These results demonstrated that the three isolated strains belong to protease-producing, moderately halophilic bacteria. Strain FAM 10, FAM 114, and FAM 115 were identified as Salinivibrio sp., Halobacillus sp., and Halobacillus sp. respectively, based on comparative analyses of the 16S rRNA gene and the 16S-23S intergenic space sequence (IGS), biochemical testing, and Gram staining. Salinivibrio sp. FAM 10 had two 16S rDNAs containing different sequences at position 191 and four IGSs that harbored no tRNA gene and tRNA genes for isoleucine, alanine, glutamate, lysine, and/or valine. Halobacillus sp. FAM 114 and FAM 115 had completely identical 16S rRNA gene sequences and showed 99% identity to the sequences of various Halobacillus strains. The three IGSs found in the genome of both strains displayed 99% sequence identity with Halobacillus aidingensis and Halobacillus sp. JM-Hb, and had $IGS^0$ with no tRNA gene and $IGS^{IA}$ with tRNA genes for isoleucine and alanine.