Bioreduction of hexavalent chromium Cr(VI) from industrial wastewater has been extensively studied because of the process’s low cost and high effectiveness. While several bacteria were found to be capable of reducing Cr(VI) to the less toxic Cr(III), reduction in the presence of other pollutants is usually not studied. This study explores the effect of other metals on the chromium reduction capabilities of the magnetotactic bacteria Magnetospirillum gryphiswaldense (MSR-1). The bioreduction ability was measured using the activity of the bacteria’s chromate reductase, an enzyme group that enables them to perform reduction from Cr(VI) directly to Cr(III). The results showed that the presence of other heavy metals significantly limited the activity of chromate reductase. Mercury was identified to be the strongest inhibitor, reducing the chromium reduction efficiency from 28.27% to 13.67%, followed by copper, zinc, and then nickel. These findings can be used to identify which heavy metals should be treated first to achieve the best chromium removal from wastewater.