The electrochemical performance of lithium-oxygen (Li-O2) batteries can be markedly improved through designing the architecture of cathode electrodes with sufficient spaces to facilitate the diffusion of oxygen and accommodate the discharge products, and optimizing the cathode catalyst to promote the oxygen reduction reaction and oxygen evolution reaction (OER). Herein, we report the synthesis of ruthenium (Ru) nanocrystal-decorated vertically aligned graphene nanosheets (VGNS) grown on nickel (Ni) foam. As an effective binder-free cathode catalyst for Li-O2 batteries, the Ru-decorated VGNS@Ni foam can significantly reduce the charge overpotential via the effects on the OER and achieve high specific capacity, leading to an enhanced electrochemical performance. The Ru-decorated VGNS@Ni foam electrode has demonstrated low charge overpotential of ~0.45 V and high reversible capacity of 23 864 mAh g−1 at the current density of 200 mA g−1, which can be maintained for 50 cycles under full charge and discharge testing condition in the voltage range of 2.0–4.2 V. Furthermore, Ru nanocrystal decorated VGNS@Ni foam can be cycled for more than 200 cycles with a low overpotential of 0.23 V under the capacity curtained to be 1000 mAh g−1 at a current density of 200 mA g−1. Ru-decorated VGNS@Ni foam electrodes have also achieved excellent high rate and long cyclability performance. This superior electrochemical performance should be ascribed to the unique three-dimensional porous nanoarchitecture of the VGNS@Ni foam electrodes, which provide sufficient pores for the diffusion of oxygen and storage of the discharge product (Li2O2), and the effective catalytic effect of Ru nanocrystals on the OER, respectively. Ex situ field emission scanning electron microscopy, X-ray diffraction, Raman and Fourier transform infrared measurements revealed that Ru-decorated VGNS@Ni foam can effectively decompose the discharge product Li2O2, facilitate the OER and lead to a high round-trip efficiency. Therefore, Ru-decorated VGNS@Ni foam is a promising cathode catalyst for rechargeable Li-O2 batteries with low charge overpotential, long cycle life and high specific capacity.