A new consortium of four bacterial isolates (Agrobacterium radiobacter; Bacillus spp.; Sphingomonas paucimobilis, and Aeromonas hydrophila)-(CM-4) was used to degrade and to decolorize triphenylmethane dyes. All bacteria were isolated from activated sludge extracted from a wastewater treatment station of a dyeing industry plant. Individual bacterial isolates exhibited a remarkable color-removal capability against crystal violet (50 mg/L) and malachite green (50 mg/L) dyes within 24 h. Interestingly, the microbial consortium CM-4 shows a high decolorizing percentage for crystal violet and malachite green, respectively, 91% and 99% within 2 h. The rate of chemical oxygen demand (COD) removal increases after 24 h, reaching 61.5% and 84.2% for crystal violet and malachite green, respectively. UV-Visible absorption spectra, FTIR analysis and the inspection of bacterial cells growth indicated that color removal by the CM-4 was due to biodegradation. Evaluation of mutagenicity by usingSalmonella typhimuriumtest strains, TA98 and TA100 studies revealed that the degradation of crystal violet and malachite green by CM-4 did not lead to mutagenic products. Altogether, these results demonstrated the usefulness of the bacterial consortium in the treatment of the textile dyes.