The stable configuration, electronic structure, magnetic property and catalytic activity of single-atom non-noble-metal (NNM) catalysts on graphene are investigated using the first-principles method. In contrast to the pristine graphene, a vacancy defect in graphene strongly stabilises the NNM adatom and makes it more positively charged. The charging leads to the CO adsorption unfavourable, while facilitate the O2 adsorption, thus alleviating the CO poisoning and improving the reaction possibility for CO oxidation. Besides, there are more electrons transferred between NNM doped-graphene and O2 molecule, which enhance their interaction and induce changes in the electronic structures and magnetic properties of the systems. Moreover, the sequential processes of CO oxidation on the Co–, Al– and Zn–graphene systems have lower enough energy barriers (<0.4 eV) by the Langmuir–Hinshelwood (LH) reaction (CO + O2 → OOCO → CO2 + Oads) than that on the Ni–graphene substrate. Among the reaction processes, the rate-controlling step is the breaking of the O–O bond of the OOCO complex to form the CO2 molecule and the atomic Oads. The results validate the reactivity of NNM catalysts at the atomic scale and initiate a clue for fabricating graphene-based catalysts with low cost and high activity.