Marine sediments polluted from anthropogenic activities can be major reservoirs of toxic mercury species. Some microorganisms in these environments have the capacity to detoxify these pollutants, by using the mer operon. In this study, we characterized microbial cultures isolated from polluted marine sediments growing under diverse environmental conditions of salinity, oxygen availability and mercury tolerance. Specific growth rates and percentage of mercury removal were measured in batch cultures for a selection of isolates. A culture affiliated with Pseudomonas putida (MERCC_1942), which contained a mer operon as well as other genes related to metal resistances, was selected as the best candidate for mercury elimination. In order to optimize mercury detoxification conditions for strain MERCC_1942 in continuous culture, three different dilution rates were tested in bioreactors until the cultures achieved steady state, and they were subsequently exposed to a mercury spike; after 24 h, strain MERCC_1942 removed up to 76% of the total mercury. Moreover, when adapted to high growth rates in bioreactors, this strain exhibited the highest specific mercury detoxification rates. Finally, an immobilization protocol using the sol-gel technology was optimized. These results highlight that some sediment bacteria show capacity to detoxify mercury and could be used for bioremediation applications.