Nanocrystalline LiMn2O4/graphene nanosheets nanocomposite has been successfully synthesized by a one-step hydrothermal method without post-heat treatment. In the nanocomposite, LiMn2O4 nanoparticles of 10–30 nm in size are well crystallized and homogeneously anchored on the graphene nanosheets. The graphene nanosheets not only provide a highly conductive matrix for LiMn2O4 nanoparticles but also effectively reduce the agglomeration of LiMn2O4 nanoparticles. The nanocrystalline LiMn2O4/graphene nanosheets nanocomposite exhibited greatly improved electrochemical performance in terms of specific capacity, cycle performance, and rate capability compared with the bare LiMn2O4 nanoparticles. The superior electrochemical performance of the nanocrystalline LiMn2O4/graphene nanosheets nanocomposite makes it promising as cathode material for high-performance lithium-ion batteries.