The aim of this work was to find a new stable laccase against inhibitors and study the decolorization ability of free and immobilized laccase on different classes of dyes. Spores from a halotolerant bacterium, Bacillus safensis sp. strain S31, isolated from soil samples from a chromite mine in Iran showed laccase activity with maximum activity at 30 °C and pH 5.0 using 2, 2-azino-bis (3-ethylbenzothiazoline-6-sulfonate) (ABTS) as the substrate. The enzyme retained about 60% of its initial activity in the presence of 10% (v v−1) methanol, ethanol, and acetone. In contrast to many other laccases, NaN3, at 0.1 and 1 mM concentrations, showed a slight inhibitory effect on the enzyme activity. Also, the spore laccase (8 U l−1) decolorized malachite green, toluidine blue, and reactive black 5 at acidic pH values; the highest decolorization percent was 75% against reactive black 5. It was observed that addition of ABTS as a redox mediator enhanced the decolorization activity. Furthermore, immobilized spore laccase encased in calcium alginate beads decolorized 95% of reactive black 5 in the absence of mediators. Overall, this isolated spore laccase might be a potent enzyme to decolorize dyes in polluted wastewaters, especially those containing metals, salts, solvents, and sodium azide.