Sulfur cathodes have much larger capacities than transition-metal-oxide cathodes used in commercial lithium-ion batteries but suffer from unsatisfactory capacity retention and long-term cyclability. Capacity degradation originates from soluble lithium polysulfides gradually diffusing into the electrolyte. Understanding of the formation and dynamics of soluble polysulfides during the discharging process at the atomic level remains elusive, which limits further development of lithium-sulfur () batteries. Here we report first-principles molecular dynamics simulations and density functional calculations, through which the discharging products of batteries are studied. We find that, in addition to simple () clusters generated from single cyclooctasulfur () rings, large clusters form by collectively coupling several different rings to minimize the total energy. At high lithium concentration, a Li-S network forms at the sulfur surfaces. The results can explain the formation of the soluble Li-S complex, such as , , and , and the insoluble and structures. In addition, we show that the presence of oxygen impurities in graphene, particularly oxygen atoms bonded to vacancies and edges, may stabilize the lithium polysulfides that may otherwise diffuse into the electrolyte.