A rate-dependent nucleation theory is developed to analyze the dependence of the capacity of lithium-sulfur (Li-S) batteries on discharge rates. The theory is based on expressing the nucleation rate of solid products in terms of the surface oversaturation of the precipitating species and rewriting the classical Kolmogorov-Avrami model in the form of a differential system of equations. By coupling this system of equations with the multicomponent transport equations we are able to explain qualitatively well the decrease of the specific capacity with increasing discharge rates and the characteristics of the discharge curves under variable discharge currents in Li-S batteries. Special attention is given to accurately determine the values of model parameters from experimental data, including the solubility constants of the solid products and the mobilities and diffusivities of the ions. The anodes of the batteries used in our analysis were made using Li foils and the cathodes were fabricated using freestanding carbon nanotube foams, on which solid sulfur was uniformly distributed to maximize the dissolution rate. The experimental data combined with the theoretical analysis show that the capacity limitation in our batteries is due to surface passivation by the final reaction products. In order to increase the specific capacity of Li-S batteries under normal discharge rates we conclude that it is better to avoid the solid precipitation of intermediate lithium polysulfides (LiPS) by using electrolytes with a high solubility of LiPS. In addition, it is better to use catalyst particles in the cathode that would promote the nucleation rate at specified locations. The number of catalyst particles should not be too small to avoid electrolyte oversaturation or too large to avoid the rapid passivation of the carbon surface with solid products.