Nitric oxide (NO) removal from a gas stream containing ~500 ppm NO was studied in a hollow fiber membrane (HFM) bioreactor. Compared to other biological NO removal methods the HFM bioreactor achieved NO removal rates that were as good if not better, of up to 92% NO removal, under comparable loadings and reactor size. Results showed that a wastewater stream containing organic carbon can be used as the electron donor to reduce the NO. Hence, combining biological NO treatment with treatment of a wastewater containing organic carbon has may be an effective overall cost-reducing strategy. The effect of different nitrate (NO3−) concentrations on the NO reduction rate was also evaluated, and results showed that NO3− does enhance the NO removal rate. The reactor’s performance was studied under six different NO:NO3− loading regimes and the NO removal rate as well as the microbial denitrifier community in the reactor was tracked. Specifically, the relevant genes responsible for each denitrification step were tracked during each different NO:NO3− loading regime to the reactor. Results showed that the denitrifying microbial community adjust rapidly to changes in the different N loadings, but overall the performance of the reactor is robust and can withstand such variability in terms of NO, NO3− and organic carbon removal.