We present the S-Band Polarization All Sky Survey (S-PASS), a survey of polarized radio emission over the southern sky at Dec~$< -1^\circ$ taken with the Parkes radio telescope at 2.3~GHz. The main aim was to observe at a frequency high enough to avoid strong depolarization at intermediate Galactic latitudes (still present at 1.4 GHz) to study Galactic magnetism, but low enough to retain ample Signal-to-Noise ratio (S/N) at high latitudes for extragalactic and cosmological science. We developed a new scanning strategy based on long azimuth scans, and a corresponding map-making procedure to make recovery of the overall mean signal of Stokes $Q$ and $U$ possible, a long-standing problem with polarization observations. We describe the scanning strategy, map-making procedure, and validation tests. The overall mean signal is recovered with a precision better than 0.5\%. The maps have a mean sensitivity of 0.81 mK on beam--size scales and show clear polarized signals, typically to within a few degrees of the Galactic plane, with ample S/N everywhere (the typical signal in low emission regions is 13 mK, and 98.6\% of the pixels have S/N $> 3$). The largest depolarization areas are in the inner Galaxy, associated with the Sagittarius Arm. We have also computed a Rotation Measure map combining S-PASS with archival data from the WMAP and Planck experiments. A Stokes $I$ map has been generated, with a sensitivity limited to the confusion level of 9 mK.