Petroleum hydrocarbons and heavy metals are some of the most widespread contaminants affecting marine ecosystems, urgently needing effective and sustainable remediation solutions. Microbial-based bioremediation is gaining increasing interest as an effective, economically and environmentally sustainable strategy. Here, we hypothesized that the heavily polluted coastal area facing the Sarno River mouth, which discharges >3 tons of polycyclic aromatic hydrocarbons (PAHs) and ∼15 tons of heavy metals (HMs) into the sea annually, hosts unique microbiomes including marine bacteria useful for PAHs and HMs bioremediation. We thus enriched the microbiome of marine sediments, contextually selecting for HM-resistant bacteria. The enriched mixed bacterial culture was subjected to whole-DNA sequencing, metagenome-assembled-genomes (MAGs) annotation, and further sub-culturing to obtain the major bacterial species as pure strains. We obtained two novel isolates corresponding to the two most abundant MAGs (Alcanivorax xenomutans strain-SRM1 and Halomonas alkaliantarctica strain-SRM2), and tested their ability to degrade PAHs and remove HMs. Both strains exhibited high PAHs degradation (60–100%) and HMs removal (21–100%) yield, and we described in detail >60 genes in their MAGs to unveil the possible genetic basis for such abilities. Most promising yields (∼100%) were obtained towards naphthalene, pyrene and lead. We propose these novel bacterial strains and related genetic repertoire to be further exploited for effective bioremediation of marine environments contaminated with both PAHs and HMs.