Azo dyes are being extensively used in textile industries, so finding a proper solution to decolorize them is of high importance. In order to find azo dye decolorizing strains among haloarchaea, which are well known for their tolerance to harsh environmental conditions, fifteen haloarchaeal strains were screened. Halogeometricum sp. strain A and Haloferax sp. strain B with the highest decolorization ability (95% and 91% for Remazol black B; both about 60% for Acid blue 161, respectively) were selected for further studies. It was shown that both strains were able to grow and decolorize the dye in a medium containing up to 5 M NaCl, with optimum decolorization activity at 2.5–3.4 M, pH 7, and a wide temperature range between 30 to 45 °C. Moreover, both strains were able to tolerate and decolorize up to 1,000 mg l−1 Remazol black B. Also, they were able to survive in 5,000 mg l−1 of the dye after 20 days' incubation. Glucose and yeast extract were found to be the best carbon and nitrogen sources in the decolorization medium for both strains. This is the first report studying decolorization of azo dyes using halophilic archaea.