High-energy-density fuel cells and metal-air batteries are difficult to commercialize on a large scale mainly because of the sluggish oxygen reduction reaction (ORR) at the cathode. Hence, the development of high-efficiency and low-cost electrocatalysts as Pt substitutes for the ORR is of significance for the mass applications of these devices. In this work, we thoroughly investigated the structural and catalytic properties of NiPd co-doped N-coordinated graphene (denoted as NiPdN6-G) as an ORR electrocatalyst by using density-functional theory (DFT) calculations. Our results show that NiPdN6-G is structurally and thermodynamically stable. Furthermore, we explored all the possible paths and intermediates of the ORR, and identified the preferable active sites and the most stable adsorption configurations of the intermediates and transition states. In general, there are 15 possible reaction paths, of which 8 paths have lower energy barriers than pure Pt, and the maximum energy barrier and overpotential of the ORR for the optimal path are only 0.14 eV and 0.37 V, respectively. This work demonstrates that NiPdN6-G should be a promising candidate for substituting Pt and Pt-based catalysts for the ORR in energy conversion and storage devices.