Direct reduction of nitrogen oxide waste gas in flue gas (COx, NOx, etc.) without NH3 injection is an ideal method to solve nitrogen oxide pollutions. The detailed reaction mechanisms of NO reduction with CO on a single Ni atom based on monolayer g-C3N4 (Ni-g-C3N4), such as Eley-Rideal, Langmuir-Hinshelwood, and termolecular Eley-Rideal, were investigated by first-principles calculation. The results indicated that Ni-g-C3N4 had excellent NO adsorption capacity and could be an active NO adsorption removal material. The termolecular Eley-Rideal was the fundamental reaction mechanism for NO reduction with a rate-determining barrier of 0.19 eV based on the thermodynamic and kinetic analysis. The intermediate N2O could be reduced to N-2 rapidly on Ni-g-C3N4 with a rate-determining barrier of 0.50 eV, and the CO in the flue gas would rapidly regenerate the oxidized Ni-g-C3N4. This work predicted a novel efficient catalyst Ni-g-C3N4 for NO reduction to N-2 with CO combining with experimental verification and provided a new insight for NO removal.