We introduce the Southern Stellar Stream Spectroscopy Survey (S^5^), an on-going program to map the kinematics and chemistry of stellar streams in the southern hemisphere. The initial focus of S^5^ has been spectroscopic observations of recently identified streams within the footprint of the dark energy survey (DES), with the eventual goal of surveying streams across the entire southern sky. Stellar streams are composed of material that has been tidally striped from dwarf galaxies and globular clusters and hence are excellent dynamical probes of the gravitational potential of the Milky Way, as well as providing a detailed snapshot of its accretion history. Observing with the 3.9m Anglo-Australian Telescope's 2-degree-Field fibre positioner and AAOmega spectrograph, and combining the precise photometry of DES DR1 with the superb proper motions from Gaia DR2, allows us to conduct an efficient spectroscopic survey to map these stellar streams. So far S^5^ has mapped nine DES streams and three streams outside of DES; the former are the first spectroscopic observations of these recently discovered streams. In addition to the stream survey, we use spare fibres to undertake a Milky Way halo survey and a low-redshift galaxy survey. This paper presents an overview of the S^5^ program, describing the scientific motivation for the survey, target selection, observation strategy, data reduction, and survey validation. Finally, we describe early science results on stellar streams and Milky Way halo stars drawn from the survey.