To achieve the green control of histamine contamination in traditionally fermented shrimp sauce, salt-tolerant strains (50 isolates) were isolated from traditional shrimp sauce from the Jiaodong Peninsula using MRS medium containing 5% NaCl. Ten non-biogenic amine-producing strains were preliminarily screened via bromocresol purple chromogenic medium. Five histamine-degrading strains were subsequently obtained by quantifying histamine degradation rates using high-performance liquid chromatography. Physiological and biochemical tests combined with 16S rDNA molecular analyses identified these strains as Bacillus albus A-1, Bacillus cereus A-2, Bacillus cereus C-3, Bacillus subtilis A-3, and Bacillus amyloliquefaciens A-4. Among them, B. subtilis A-3 exhibited the optimal degradation capacity (26.67% in vitro degradation rate) and robust environmental adaptability. Safety assessments confirmed its non-hemolytic activity, complete susceptibility to nine antibiotics (including ampicillin), and antibacterial activity against Escherichia coli (inhibition zone diameter: 12.75 mm). When applied in the rapid fermentation of Antarctic krill sauce, this strain significantly reduced the histamine content to 12.36 μg•mL-1 (38.35% degradation rate). The sensory qualities were enhanced, as verified through a quantitative descriptive analysis (QDA) and electronic nose analysis. B. subtilis A-3, which integrates a high-efficiency degradation capability, environmental adaptability, and biosafety, provides a reliable microbial resource and technical foundation for the safe production of shrimp sauce.