The gut microbiota enriches the human gene pool and contributes to xenobiotic metabolism. Microbial azoreductases modulate the reduction of azo-bonds, activating produgs and azo polymer-coated dosage forms, or degrading food additives. Here, we aimed to screen the healthy human gut microbiota for food colorant-reducing activity and to characterize factors modulating it. Four representative isolates from screened fecal samples were identified as E. coli (AZO-Ec), E. faecalis (AZO-Ef), E. avium (AZO-Ev) and B. cereus (AZO-Bc). Both AZO-Ef and AZO-Ev decolorized amaranth aerobically and microaerophilically while AZO-Ec and AZO-Bc had higher aerobic reduction rates. The isolates varied in their activities against different dyes, and the azo-reduction activity mostly followed zero-order reaction kinetics, with a few exceptions. Additionally, the isolates had different pH dependence, e.g., AZO-Ec was not affected by pH variation while AZO-Bc exhibited variable degradation kinetics at different pH levels. Cell-free extracts showed NADH-dependent enzymatic activities 14–19 times higher than extracellular fractions. FMN did not affect the reducing activity of AZO-Ef cell-free extract, whereas AZO-Ec, AZO-Ev and AZO-Bc had significantly higher reduction rates in its presence (P values = 0.02, 0.0001 and 0.02, respectively). Using Degenerate primers allowed the amplification of azoreductase genes, whose sequences were 98–99% similar to genes encoding FMN-dependent-NADH azoreductases.