This work reported the full degradation of an azo dye in a synthetic effluent by Pseudomonas oleovorans immobilized in polyurethane foam (PUF). For each fed-batch experiment, a screw-top vessel containing 160 mL of nutrient broth was inoculated with 0.16 g L−1 of fresh culture, incubated at 32 °C and supplemented with 50 mg L−1 of dye every 24 hours. Afterwards, the P. oleovorans were immobilized in PUF and inoculated in an anoxic reactor. The results showed that at fed-batch conditions, P. oleovorans was capable of removing 50 mg of dye in 192 hours. However, when the decolorization was performed in an anoxic reactor, it was capable of fully degrading 25 mg of dye in only 24 hours.