Mangrove forests are ecosystems with highly diverse microorganisms. We aimed to obtain bacterial isolates from mangrove water forests and determine their bacterial diversity and potential for decoloring dye waste. Bacteria were isolated from three sites in the Belawan mangrove forest of North Sumatra. Bacteria were isolated on nutrient agar media. Twenty-nine bacterial strains were isolated, purified, and molecularly identified at the species level. The isolates belonged to 8 genera consisting of 15 species: Aeromonas caviae, Aeromonas salmonicida, Bacillus anthracis, Bacillus cereus, Bacillus mycoides, Enterobacter cloacae, Enterobacter kobei, Klebsiella pneumoniae, Myroides profundi, Providencia huaxiensis, Pseudomonas balearica, Pseudomonas hydrolytica, Pseudomonas khazarica, Shigella flexneri, and Shigella sonnei. Decolorization activity screening was performed in a solid mineral salt medium (MSM) containing 25%, 50%, 75%, and 100% dye waste. Based on colony diameter, the following five out of twenty-nine isolates showed a higher growth response: S. flexneri, B. cereus, A. salmonicida, K. pneumoniae, and E. cloacae. The waste decolorization ability of these five species was quantitatively determined in liquid MSM containing 50% dye waste. All isolates decolorized >15% dye after 15 days, and A. salmonicida and E. cloacae exhibited relatively better decolorization activity than that of the other three strains.