As one of the most important research areas in lithium-ion batteries (LIBs), well-designed nanostructures have been regarded as key for solving problems such as lithium ion diffusion, the collection and transport of electrons, and the large volume changes during cycling processes. Here, hierarchical graphene-wrapped TiO2@Co3O4 coaxial nanobelt arrays (G-TiO2@Co3O4 NBs) have been fabricated and further investigated as the electrode materials for LIBs. The results show that the yielded G-TiO2@Co3O4 NBs possess a high reversible capacity, an outstanding cycling performance, and superior rate capability compared to TiO2 and TiO2@Co3O4 nanobelt array (TiO2@Co3O4 NBs) electrodes. The core–shell TiO2@Co3O4 NBs may contain many cavities and provide more extra spaces for lithium ion storage. The introduction of graphene into nanocomposite electrodes is favorable for increasing their electrical conductivity and flexibility. The integration of hierarchical core–shell nanobelt arrays and conducting graphene may induce a positive synergistic effect and contribute to the enhanced electrochemical performances of the electrode. The fabrication strategy presented here is facile, cost-effective, and can offer a new pathway for large-scale energy storage device applications.