In this study Bacillus thuringiensis 4G1 was used to decolorize Methylene Blue (MB). The decolorization process was optimized by using two sequential experimental designs. Eleven fermentation factors were screened using Plackett-Burman design. Among these factors, the most significant variables influencing MB decolorization were statistically elucidated for optimization and included MgSO4.7H2O, glucose and (NH4)2 SO4. The optimum concentrations of these variables were predicted by using a second order polynomial model fitted to the results obtained by applying the Box-Behnken design. A verification experiment performed under optimal conditions yielded 98.23% of the predicted decolorization% (100%) with an increase by a factor of 1.3 compared with the results obtained under basal conditions.