The present study emphasizes on the decolorization of malachite green using Pseudomonas putida. The effect of pH, temperature, dye concentration, inoculum volume and static/agitated condition was studied using One Factor At a Time approach. Malachite green was decolorized by around 90% with this bacterium and the optimal conditions were found to be pH 7, 30°C, 200 mg/L dye concentration, 0.5 mL inoculum under the static condition. Response Surface Methodology using Box Behnken Design was applied to further optimize malachite green decolorization. A quadratic model was obtained for dye decolorization through this design. The optimum values for temperature, dye concentration, incubation time and inoculum volume were found to be 25°C, 200 mg/L, 72 hours and 0.75 mL respectively. The predicted decolorization rate under the optimum conditions determined by Response Surface Methodology was in close agreement with the experimental results and the model was found to be significant. The germination and growth of Triticum aestivum and Vigna radiata seeds and the growth of micro-organisms were not inhibited by the degraded metabolic products of the dye in the toxicity studies. The ability of the strain to tolerate, decolorize and degrade malachite green at high concentration gives it an advantage for the treatment of textile industry wastewater. This approach creates a promising hope for the bioremediation of the environment which is polluted by hazardous dyes.