Investigations on the ability of bacteria to enhance removal of hydrocarbons and reduce heavy metal toxicity in sediments are necessary to design more effective bioremediation strategies. In this study, five bacterial strains, Halomonas sp. SZN1, Alcanivorax sp. SZN2, Pseudoalteromonas sp. SZN3, Epibacterium sp. SZN4, and Virgibacillus sp. SZN7, were isolated from polluted sediments from an abandoned industrial site in the Gulf of Naples, Mediterranean Sea, and tested for their bioremediation efficiency on sediment samples collected from the same site. These bacteria were added as consortia or as individual cultures into polluted sediments to assess biodegradation efficiency of polycyclic aromatic hydrocarbons and heavy metal immobilisation capacity. Our results indicate that these bacteria were able to remove polycyclic aromatic hydrocarbons, with a removal rate up to ca. 80% for dibenzo-anthracene. In addition, these bacteria reduced arsenic, lead, and cadmium mobility by promoting their partitioning into less mobile and bioavailable fractions. Microbial consortia generally showed higher performance toward pollutants as compared with pure isolates, suggesting potential synergistic interactions able to enhance bioremediation capacity. Overall, our findings suggest that highly polluted sediments select for bacteria efficient at reducing the toxicity of hazardous compounds, paving the way for scaled-up bioremediation trials