We provide a rigorous proof that the Hohenberg-Kohn theorem holds for spin densities by extending Lieb's Legendre-transform formulation to spin densities. The resulting spin-density-functional theory resolves several troublesome issues. Most importantly, the present paper provides an explicit construction for the spin potentials at any point along the adiabatic connection curve, thus providing a formal basis for the use of exchange-correlation functionals of the spin density in the Kohn-Sham density-functional theory (DFT). The practical implications of this result for unrestricted Kohn-Sham DFT calculations is considered, and the existence of holes below the Fermi level is discussed. We argue that an orbital's energy tends to increase as its occupation number increases, which provides the basis for a computational algorithm for determining the occupation numbers in Kohn-Sham DFT and helps explain the origin of Hund's rules and holes below the Fermi level.