Bioremediation of pollutants such as heavy metals is an economic and environmentally friendly process. A novel molybdenum-reducing bacterium was isolated and characterized for its potential to reduce hexavalent molybdenum to molybdenum blue (Mo-blue). The bacterium reduces molybdate optimally at pH between 6 and 8, temperature between 35 and 40 ËšC. Glucose was the best electron donor source supporting molybdate reduction followed by sucrose, fructose, starch and glycerol in descending order. Other requirements include optimum phosphate concentration at 5.0 mM and molybdate concentration between 20 and 40 mM. 16S rRNA partial sequencing and phylogenetic analysis identified the bacterium as Pantoea sp. strain HMY-P4. The capacity of this bacterium to reduce toxic soluble molybdenum to a less toxic form is novel and makes the bacterium an important instrument for bioremediation of this pollutant.