Electrochemical double-layer capacitor (EDLC) electrodes are conventionally based on carbon materials, which provide increased chemical stability and the possibility of a large number of charge and discharge cycles. However, their specific capacitance is generally much lower than pseudo-capacitors based on metal oxide or conductive polymer electrodes. Carbon-based electrodes for electrochemical devices can be hybridized with metal oxide functionalities in order to provide catalytic activity that increases their electrochemical performances. We report the preparation of a conductive hybrid electrode of reduced graphene oxide and molybdenum oxide by a facile one-pot hydrothermal synthesis. A three-dimensional network structure comprising graphene and molybdenum oxide was obtained when phosphomolybdic acid was used as a precursor for molybdenum oxide. The hybrid material contains polycrystalline nanoparticles of molybdenum (IV) oxide (MoO2) that covers the surface of reduced graphene oxide. Compared to graphene electrodes, the hybrid electrodes showed significantly improved specific capacitance, as good as three times higher (381 vs. 140 F/g), and considerable reduction of the equivalent series resistance (by about half) when they were used in a supercapacitor with sodium containing aqueous electrolyte.