Thirteen bacterial isolates from a bioreactor treating a mixture of municipal and molasses wastewater were investigated for their potential to degrade and decolorize melanoidins. All isolates were initially screened for manganese peroxidase activity and growth potential in the presence of four synthetic melanoidins solutions at concentrations ranging from 3 to 7 g/L/L. Three isolates of potential manganese peroxidase-producing bacteria two Klebsiella sp. (B2–B3) and Escherichia coli (B4) and one strain of Lactobacillus kefiri (B1) showed high synthetic melanoidin tolerance. The 16S rDNA sequence showed that they were closely related to E. coli and Klebsiella sp. The most significant degree of decolorization was observed on day 1, reaching 60–67%. Furthermore, the tested strains reduced the chemical oxygen demand by more than 50% or more than 70% of the initial value with or without additional supplementation of the reaction mixture, respectively. All tested isolates showed increased ability for reducing the organic matter content of a raw melanoidin solution exceeding 65%, favouring, therefore, the utilization potential of the isolated strains for the biological processing of molasses wastewaters. Thus, microbial decolorization could be an innovative wastewater treatment for environmental protection purposes.