Display omitted •The screened M-G structures are very thermodynamically stable, and the stability is even higher than that of the corresponding bulk metal surfaces.•The binding energies of ORR intermediates suggest that they are not linear dependence, which are different form the cases found on some metal-based catalysts.•The Au-, Co-, and Ag-G structures could be used as the ORR catalysts. Graphene doping is a promising direction for developing effective oxygen reduction reaction (ORR) catalysts. In this paper, we computationally investigated the ORR performance of 10 kinds of metal-doped graphene (M-G) catalysts, namely, Al-, Si-, Mn-, Fe-, Co-, Ni-, Pd-, Ag-, Pt-, and Au-G. The results shown that the binding energies of the metal atoms incorporated into the graphene vacancy are higher than their bulk cohesive energies, indicating the formed M-G catalysts are even more stable than the corresponding bulk metal surfaces, and thus avoid the metals dissolution in the reaction environment. We demonstrated that the linear relation among the binding energies of the ORR intermediates that found on metal-based materials does not hold for the M-G catalysts, therefore a single binding energy of intermediate alone is not sufficient to evaluate the ORR activity of an arbitrary catalyst. By analysis of the detailed ORR processes, we predicted that the Au-, Co-, and Ag-G materials can be used as the ORR catalysts.