A combination of electrodeposition and carbonation techniques was adopted to deposit reduced graphene oxide films on TiO2 nanotube arrays (RGO-TiO2 NTAs), which were prepared by two-step electrochemical anodization in ethylene glycol system. The RGO-TiO2 NTAs exhibit a significantly enhanced photocatalytic degradation ability for methyl orange (MO) than pristine TiO2 NTAs and annealed TiO2 NTAs under the same conditions. The kinetic constant for the photocatalytic degradation of MO using RGO-TiO2 NTAs prepared by annealing in an Ar atmosphere at 550 °C was 2.9 times higher than that using the pristine TiO2 NTAs. The highly efficient photocatalytic activity is attributed to the enhanced separation efficiency of photoinduced electrons and holes, the red shift of the absorption band in the UV region as well as the strong adsorption ability of RGO towards MO molecules. This proposed facile strategy provides a promising avenue to synthesize novel TiO2 NTAs-based hybrid materials for efficient photocatalysis in the future.