The aim of the present study is to study the catalytic activity of Ni-doped graphene in the reduction of NO by CO molecule. The adsorption energies, geometric parameters, reaction barriers, and thermodynamic properties are calculated using the M06-2X density functional. The results suggest that the reaction proceeds in two steps, initiating by the co-adsorption of two CO molecules over the surface, followed by the addition of NO molecules to form a stable (OCON)2 intermediate. Next, by overcoming a small activation energy, a N2 molecule is formed which can easily desorb from the surface due to its negligible adsorption energy. Finally, two CO2 molecules are formed over the surface, which need a negligible activation energy. According to our results, the Ni-doped graphene can be used as a potential catalyst for the NO reduction by CO molecule. These theoretical results could be also useful in practical applications for removal of toxic NO and CO molecules.