In this study, initially 11 different bacterial strains were tested for the degradation capabilities against Basic Orange 2 dye. In initial screening with 78.90% degradation activity, Escherichia coli emerged as the most promising strain to degrade the selected dye, and was then employed in subsequent experiments. For further enhancing the degradation capability of selected bacteria, the effects of various physicochemical parameters were also evaluated. Among the tested parameters, 20 ppm dye concentration, 1666 mg/L glucose concentration, a temperature of 40 °C, 666 mg/L sodium chloride concentration, pH 7, 1000 mg/L urea concentration, a 3-day incubation period and the use of sodium benzoate as a redox mediator (666 mg/L) were found to be ideal conditions to get the highest decolorization/degradation activities. Finally, all the mentioned parameters were combined in a single set of experiments, and the decolorization capacity of the bacteria was enhanced to 89.88%. The effect of pH, dye concentration, incubation time and temperature were found to be responsible for the optimum degradation of dye (p < 0.05), as predicted from the ANOVA (analysis of variance) of the response surface methodology. The metabolites were collected after completion of the process and characterized through Fourier transform irradiation (FTIR) and gas chromatography mass spectrometry (GC-MS). From the data obtained, a proposed mechanism was deduced where it was assumed that the azo bond of the dye was broken by the azoreductase enzyme of the bacteria, resulting in the formation of aniline and 3, 4-diaminobezeminium chloride. The aniline was then further converted to benzene by deamination by the action of the bacterial deaminase enzyme. The benzene ring, after subsequent methylation, was transformed into o-xylene, while 3, 4-diaminobezeminium chloride was converted to p-xylene by enzymatic action. These findings suggest that Escherichia coli is a capable strain to be used in the bioremediation of textile effluents containing azo dyes. However, the selected bacterial strain may need to be further investigated for other dyes as well.