We present the first spectroscopic measurements of the ATLAS and Aliqa Uma streams from the Southern Stellar Stream Spectroscopic Survey ($S^5$), in combination with the photometric data from the Dark Energy Survey and astrometric data from $Gaia$. From the coherence of spectroscopic members in radial velocity and proper motion, we find out that these two systems are physically one stream with discontinuity in morphology and density on the sky (the "kink" feature). We refer to this entire stream as ATLAS-Aliqa Uma stream, or AAU stream. We perform a comprehensive exploration of the effect of baryonic substructures and find that only an encounter with the Sagittarius dwarf $\sim 0.5$ Gyr ago can create a feature similar to the observed "kink". In addition, we also identify two gaps in the ATLAS component associated with the broadening in the stream width (the "broadening" feature). These gaps have likely been created by small mass perturbers, such as dark matter halos, as AAU stream is the most distant cold stream known with severe variations in both the stream surface density and the stream track on the sky. With the stream track, stream distance and kinematic information, we determine the orbit of the AAU stream and find that it has been affected by the Large Magellanic Cloud, resulting in a misalignment between the proper motion and stream track. Together with the Orphan-Chenab Stream, AAU is the second stream pair that has been found to be a single stream separated into two segments by external perturbation.

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.9-m 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 9 DES streams and 3 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. Updates on ${S}^5$, including future public data release, can be found at \url{http://s5collab.github.io}.