The fabrication of β-CoV3O8 nanorods embedded in graphene sheets and their application as electrochemical charge storage electrodes is reported. From the surfactant treatment of raw graphite, graphene was directly prepared and its nanocomposite with β-CoV3O8 nanorods distributed between graphene layers (β-CoV3O8-G) was synthesized by a hydrothermal method. When applied as an anode in lithium-ion batteries, the β-CoV3O8-G anode exhibits greatly improved charge and discharge capacities of 790 and 627 mAh · g-1, respectively, with unexpectedly high initial efficiency of 82%. The observed discharge capacity reflected that at least 3.7 mol of Li+ is selectively accumulated within the β-CoV3O8 phase (LixCoV3O8, x > 3.7), indicative of significantly improved Li+ uptake when compared with aggregated β-CoV3O8 nanorods. Moreover, very distinct peak plateaus and greatly advanced cycling performance are observed, showing more improved Li+ storage within the β-CoV3O8 phase. As a supercapacitor electrode, moreover, our composite electrode exhibits very high peak pseudocapacitances of 2.71 F · cm-2 and 433.65 F · g-1 in the β-CoV3O8 phase with extremely stable cycling performance. This remarkably enhanced performance in the individual electrochemical charge storage electrodes is attributed to the novel phase formation of β-CoV3O8 and its optimized nanocomposite structure with graphene, which yield fast electrical conduction through graphene, easy accessibility of ions through the open multilayer nanosheet structure, and a relaxation space between the β-CoV3O8-G.