Although lithium ion batteries have gained commercial success owing to their high energy density, they lack suitable electrodes capable of rapid charging and discharging to enable a high power density critical for broad applications. Here, we demonstrate a simple bottom-up approach toward single crystalline vanadium oxide (VO2) ribbons with graphene layers. The unique structure of VO2-graphene ribbons thus provides the right combination of electrode properties and could enable the design of high-power lithium ion batteries. As a consequence, a high reversible capacity and ultrafast charging and discharging capability is achieved with these ribbons as cathodes for lithium storage. A full charge or discharge is capable in 20 s. More remarkably, the resulting electrodes retain more than 90% of the initial capacity after cycling more than 1000 times at an ultrahigh rate of 190C, providing the best reported rate performance for cathodes in lithium ion batteries to date.