Background: Mercury-polluted environments are often contaminated with other heavy metals. Therefore, bacteria with resistance to several heavy metals may be useful for bioremediation. Cupriavidus metallidurans CH34 is a model heavy metal-resistant bacterium, but possesses a low resistance to mercury compounds. Methodology/Principal Findings: To improve inorganic and organic mercury resistance of strain CH34, the IncP-1β plasmid pTP6 that provides novel merB, merG genes and additional other mer genes was introduced into the bacterium by biparental mating. The transconjugant Cupriavidus metallidurans strain MSR33 was genetically and biochemically characterized. Strain MSR33 maintained stably the plasmid pTP6 over 70 generations under non-selective conditions. The organomercurial lyase protein MerB and the mercuric reductase MerA of strain MSR33 were synthesized in presence of Hg2+. The minimum inhibitory concentrations (mM) for strain MSR33 were: Hg2+, 0.12 and CH3Hg+, 0.08. The addition of Hg2+ (0.04 mM) at exponential phase had not an effect on the growth rate of strain MSR33. In contrast, after Hg2+ addition at exponential phase the parental strain CH34 showed an immediate cessation of cell growth. During exposure to Hg2+ no effects in the morphology of MSR33 cells were observed, whereas CH34 cells exposed to Hg2+ showed a fuzzy outer membrane. Bioremediation with strain MSR33 of two mercury-contaminated aqueous solutions was evaluated. Hg2+ (0.10 and 0.15 mM) was completely volatilized by strain MSR33 from the polluted waters in presence of thioglycolate (5 mM) after 2 h. Conclusions/Significance: A broad-spectrum mercury-resistant strain MSR33 was generated by incorporation of plasmid pTP6 that was directly isolated from the environment into C. metallidurans CH34. Strain MSR33 is capable to remove mercury from polluted waters. This is the first study to use an IncP-1β plasmid directly isolated from the environment, to generate a novel and stable bacterial strain useful for mercury bioremediation.