Hexavalent chromium ($Cr^{6+}$) is a highly harmful pollutant, which can be detoxified and precipitated through reduction to $Cr^{3+}$. Bacillus megaterium TKW3 previously isolated from chromium-contaminated marine sediments was capable of reducing $Cr^{6+}$ in concomitance with metalloids ($Se^{4+}$, $Se^{6+}$, and $As^{5+}$). Notwithstanding approximately 50% inhibition, it was the first report of simultaneous bacterial reduction of $Cr^{6+}$ and $Se^{4+}$ (to elemental Se). No significant difference was observed among electron donors (glucose, maltose, and mannitol) on $Cr^{6+}$ reduction by B. megaterium TKW3. The reduction was constitutive and determined to be non-plasmid mediated. Peptide mass fingerprints (PMF) revealed a novel aerobic membrane-associated reductase with $Cr^{6+}$-induced expression and specific reductive activity (in nmol $Cr^{6+}$/mg protein/min) of 0.220 as compared with 0.087 of the soluble protein fraction. Respiratory inhibitor $NaN_3$ did not interfere with the reductase activity. Transmission electron microscopy with energy dispersive X-ray (TEM-EDX) analysis confirmed the aggregation of reduced chromium along the intracellular membrane region. Future identification of the N-terminal amino acid sequence of this reductase will facilitate purification and understanding of its enzymatic action.