Ultrafine Co3O4 nanocrystals homogeneously attached to nitrogen doped reduced graphene oxide (rGO) by the hydrothermal reaction method are demonstrated as anode materials for lithium ion batteries. Transmission electron microscope images revealed that the crystal size of Co3O4 in Co3O4/N-rGO and Co3O4/rGO is 5-10 nm, much smaller than that of bare Co3O4, indicating that the reduced graphene oxide sheets with Co3O4 nanocrystals attached could hinder the growth and aggregation of Co3O4 crystals during synthesis. The graphene sheets can also effectively buffer the volume change of Co3O4 upon lithium insertion/extraction, thus improving the cycling performance of the composite electrodes. The doped nitrogen on the reduced graphene oxide can not only improve the conductivity of the graphene sheets, but also introduce defects to store lithium and enhance the connection of the Co3O4 nanocrystals to the graphene sheet, leading to better distribution of Co3O4 on the graphene sheets, and enhanced rate performance. The nitrogen doping combined with the unique structural features is a promising strategy for the development of electrode materials for lithium ion batteries with high electrochemical performance.