Nanocomposite consisting of ultrafine, cobalt carbonate nanoneedles and 3D porous graphene aerogel (CoCO3/GA) are in situ synthesized based on a one-step hydrothermal route followed by freeze drying. A further heat treatment produces cobalt oxide nanoparticles embedded in the conductive GA matrix (Co3O4/GA). Both the composite anodes deliver excellent specific capacities depending on current density employed: the CoCO3/GA anode outperform the Co3O4/GA anode at low current densities, and vice versa at current densities higher than 500 mA g-1. Their electrochemical performances are considered among the best of similar composite anodes consisting of CoCO3 or Co3O4 active particles embedded in a graphene substrate. The stable multi-step electrochemical reactions of the carbonate compound with a unique nanoneedle structure contribute to the excellent cyclic stability of the CoCO3/GA electrode, whereas the highly conductive networks along with low charge transfer resistance are responsible for the high rate performance of the Co3O4/GA electrode.