Mangroves in the Northwest Coast of South America are contaminated with heavy metals due to wastewater discharges from industries, affecting the biota from this environment. However, bacteria proliferate in these harsh environmental conditions becoming possible sentinel of these contaminations. In this study, bacterial community composition was analyzed by throughput sequencing of the 16S rRNA gene from polluted and pristine mangrove sediments affected by marked differences in heavy metal concentrations. Core bacteria were dominated by Proteobacteria, Firmicutes, and Bacteroidetes phyla, with strong differences between sites at class and genus levels, correlated with metal levels. Increment of abundance on specific OTUs were associated with either elevated or decreased concentrations of metals and with the sulfur cycle. The abundance of Sulfurovum lithotrophicum, Leptolinea tardivitalis, Desulfococcus multivorans and Aminobacterium colombiense increases when metals rise. On contrary, Bacillus stamsii, Nioella nitrareducens and Clostridiisalibacter paucivorans abundance in- creases when metal levels are reduced. We propose these OTUs as bacterial sentinels, whose abundance can help monitor the restoration programs of contaminated mangrove sediments in the future.