A bio-trickling filter (BTF) packed with polyhedral spheres was used to remove nitrogen oxides (NOx) from the flue gas of a coal-fired power plant. The BTF system consistently removed 64–95% of the NOx after start-up and acclimation under dynamic conditions (e.g., 120–240 m3/h flue gas flow rate and inlet 300–900 mg NOx/m3). Scanning electron microscopy of the biofilms that were formed showed a shift in the predominating bacteria. Analyses by PCR-denaturing gradient gel electrophoresis showed that the naturally-selected mixed cultures in the biofilm under a flue gas environment were mainly Klebsiella sp. and Pseudomonas sp.