Graphene nanosheets (GNS) with attached MnOx nanoparticles are studied in regard to their structure and morphology. The relationship between the lithium storage performances and GNS contents as well as manganese valency was investigated. Experimental results showed that the specimen with 44 wt% GNS and high content of MnO delivered high reversible capacity (over twice of that in graphitic carbon anode), good cycling stability (0.8% fading per cycle), and high rate capability (67% at the 800 mA/g), which are dramatically better than pure Mn3O4. The improvement is attributed to the presence of GNS which provides continuous networks for fast electronic conduction and mechanical flexibility for accommodating the large volume change. The MnOx/GNS hybrid material has the added advantages over pure GNS, benefiting from its lithium storage potential of around 0.5 V which not only ensures high rate capability but also reduces the risk of metallic lithium formation with its safety hazard.