Graphene-decorated V2O5 nanobelts (GVNBs) were synthesized via a low-temperature hydrothermal method in a single step. V2O5 nanobelts (VNBs) were formed in the presence of graphene oxide, a mild oxidant, which also enhanced the conductivity of GVNBs. From the electron energy loss spectroscopy analysis, the reduced graphene oxide (rGO) are inserted into the layered crystal structure of V2O5 nanobelts, which further confirmed the enhanced conductivity of the nanobelts. The electrochemical energy-storage capacity of GVNBs was investigated for supercapacitor applications. The specific capacitance of GVNBs was evaluated using cyclic voltammetry (CV) and charge/discharge (CD) studies. The GVNBs having V2O5-rich composite, namely, V3G1 (VO/GO = 3:1), showed superior specific capacitance in comparison to the other composites (V1G1 and V1G3) and the pure materials. Moreover, the V3G1 composite showed excellent cyclic stability and the capacitance retention of about 82% was observed even after 5000 cycles.