The Stromlo-APM Redshift Survey consists of 1797 galaxies with {ital b}{sub {ital J}}{le}17.15 selected randomly, at a rate of 1 in 20 from automated plate measurement (APM) scans. The survey covers a solid angle of 1.3 sr (4300 deg{sup 2}) in the south Galactic cap. Redshifts have been measured for 1790 (99.6{percent}) of the galaxies. The median galaxy recession velocity is 15,300 km s{sup {minus}1}, and so the volume probed is {ital V}{approx_equal}1.38{times}10{sup 6} h{sup {minus}3} Mpc{sup 3}. In this paper we describe the construction of the redshift catalog and present the survey data. {copyright} {ital 1996 The American Astronomical Society.}