The cathodic oxygen reduction reaction (ORR) is essential in the electrochemical energy conversion of fuel cells. Here, through the NH3 atmosphere annealing of a graphene oxide (GO) precursor containing trace amounts of Ru, we have synthesized atomically dispersed Ru on nitrogen-doped graphene that performs as an electrocatalyst for the ORR in acidic medium. The Ru/nitrogen-doped GO catalyst exhibits excellent four-electron ORR activity, offering onset and half-wave potentials of 0.89 and 0.75 V, respectively, vs a reversible hydrogen electrode (RHE) in 0.1 M HClO4, together with better durability and tolerance toward methanol and carbon monoxide poisoning than seen in commercial Pt/C catalysts. X-ray adsorption fine structure analysis and aberration-corrected high-angle annular dark-field scanning transmission electron microscopy are performed and indicate that the chemical structure of Ru is predominantly composed of isolated Ru atoms coordinated with nitrogen atoms on the graphene substrate. Furthermore, a density function theory study of the ORR mechanism suggests that a Ru-oxo-N4 structure appears to be responsible for the ORR catalytic activity in the acidic medium. These findings provide a route for the design of efficient ORR single-atom catalysts.