Ultralong, as long as ∼1 mm, orthorhombic vanadium pentoxide (V2O5) nanowires were synthesized using a hydrothermal method. Free-standing and binder-free composite paper was prepared on a large scale by a two-step reduction method using free-standing V2O5 nanowires as the skeleton and reduced graphene oxide (rGO) nanosheets as the additive. Such a free-standing V2O5/rGO composite paper as a cathode for lithium ion batteries possesses both structural integrity and extraordinary electrochemical performance. The reversible specific areal capacity of the V2O5/rGO composite paper electrode is 885 μAh/cm2 at 0.09 mA/cm2, much higher than that of the pure V2O5 nanowire paper electrode (570 μAh/cm2). It also shows excellent cycling performance at high rates with 30.9% loss of its initial capacities after 1000 cycles at a current rate of 0.9 mA/cm2. The excellent performance was attributed to the improved electronic conductivity and Li+ ion transport from the rGO addition.