The prokaryotic diversity associated with highly metal-contaminated sediment samples collected from the Coeur d'Alene River (CdAR) was investigated using a cultivation-independent approach. Bacterial community structure was studied by constructing an RNA polymerase beta subunit (rpoB) gene library. Phylogenetic analysis revealed that 75.8% of the rpoB clones were associated with beta-Proteobacteria while the remaining 24.2% were with gamma-Proteobacteria. All phylotypes showed close similarity to previously reported cultivable lineages from metal or organic contaminant-rich environments. In an archaeal 16S rRNA gene library, 70% of the clones were affiliated to Crenarchaeota, while 30% belonged to Euryarchaeota. Most of the Euryarchaeota sequences were related to acetoclastic lineages belonging to Methanosarcinales. A single phylotype within the Euryarchaeota showed no association with cultivable euryarchaeotal lineages and might represent novel taxon. Diversity indices demonstrated greater diversity of Bacteria compared to Archaea in CdAR sediments. Sediment characterization by the X-ray fluorescence spectroscopy revealed high amount of toxic metals. To our knowledge, this is the first culture-independent survey on the prokaryotic diversity present in mining-impacted sediments of CdAR.