Sulfate-reducing bacteria (SRB) are often used in bioremediation of acid mine drainage because microbial sulfate reduction increases pH and produces sulfide that binds with metals. Mercury methylation has also been linked with sulfate reduction. Previous geochemical analysis indicated the occurrence of sulfate reduction in mine tailings, but no molecular characterization of the mine tailings-associated microbial community has determined which SRB are present. This study characterizes the bacterial communities of two geochemically contrasting, high-methylmercury mine tailing environments, with emphasis on SRB, by analyzing small subunit (SSU) rRNA genes present in the tailings sediments and in enrichment cultures inoculated with tailings. Novel Deltaproteobacteria and Firmicutes-related sequences were detected in both the pH-neutral gold mine tailings and the acidic high-sulfide base-metal tailings. At the subphylum level, the SRB communities differed between sites, suggesting that the community structure was dependent on local geochemistry. Clones obtained from the gold tailings and enrichment cultures were more similar to previously cultured isolates whereas clones from acidic tailings were more closely related to uncultured lineages identified from other acidic sediments worldwide. This study provides new insights into the novelty and diversity of bacteria colonizing mine tailings, and identifies specific organisms that warrant further investigation with regard to their roles in mercury methylation and sulfur cycling in these environments.