First principles studies combined with the microkinetic analysis were performed to study the reliability and reaction mechanisms of single-atom doped graphene (SADGr) materials in catalyzing NOx reduction with CO. By screening the 3d transition metals (Sc-Zn) and group-IV elements (Si and Ge), it was found that the Ti and Co doped graphene sheets (TiGr and CoGr) respectively own excellent catalytic activities in the NO/NO2-to-N2O and the N2O-to-N2 processes at low temperatures. Therefore, the TiGr/CoGr composite can be a promising catalyst in NOx reduction with CO. It was further revealed the combination of adsorption energy and electronegativity was a good descriptor to predict the activation energies. The obtained results can provide useful information for rational design of carbon-based single-atom catalysts for NOx reduction by CO at low temperatures.