Rechargeable lithium-sulfur batteries having a cathode that includes a graphene-sulfur nanocomposite can exhibit improved characteristics. The graphene-sulfur nanocomposite can be characterized by graphene sheets with particles of sulfur adsorbed to the graphene sheets. The sulfur particles have an average diameter less than 50 nm.