The role of microbial processes in bioaccumulation of major and trace elements has been broadly demonstrated. However, microbial communities from marine sediments have been poorly investigated to this regard. In marine environments, particularly under high anthropogenic pressure, heavy metal accumulation increases constantly, which may lead to significant environmental issues. A better knowledge of bacterial diversity and its capability to bioaccumulate metals is essential to face environmental quality assessment. The oligotrophic westernmost Mediterranean, which is highly sensitive to environmental changes and subjected to increasing anthropogenic pressure, was selected for this study. A sediment core spanning the last two millennia was sampled at two intervals, with ages corresponding to 140 (S1) and 1400 (S2) yr BP. High-throughput sequencing showed an abundance of Bacillus, Micrococcus, unclassified members of Planococcaceae, Anaerolineaceae, Planctomycetaceae, Microlunatus, and Microbacterium in both intervals, with slight differences in their abundance, along with newly detected ones in S2, i.e., Propionibacterium, Fictibacillus, Thalassobacillus, and Bacteroides. Canonical correspondence analysis (CCA) and co-occurrence patterns confirmed strong correlations among the taxa and the environmental parameters, suggesting either shared and preferred environmental conditions, or the performance of functions similar to or complementary to each other. These results were further confirmed using culture-dependent methods. The diversity of the culturable bacterial community revealed a predominance of Bacillus, and Micrococcus or Kocuria. The interaction of these bacterial communities with selected heavy metals (Cu, Cr, Zn and Pb) was also investigated, and their capacity of bioaccumulating metals within the cells and/or in the extracellular polymeric substances (EPS) is demonstrated. Interestingly, biomineralization of Pb resulted in the precipitation of Pb phosphates (pyromorphite). Our study supports that remnants of marine bacterial communities can survive in deep-sea sediments over thousands of years. This is extremely important in terms of bioremediation, in particular when considering possible environmentally friendly strategies to bioremediate inorganic contaminants.