The Parkes Galactic All-Sky Survey (GASS) is a survey of Galactic atomic hydrogen (HI) emission in the Southern sky covering declinations $delta leq 1^{circ}$ using the Parkes Radio Telescope. The survey covers $2pi$ steradians with an effective angular resolution of ~16, at a velocity resolution of 1.0 km/s, and with an rms brightness temperature noise of 57 mK. GASS is the most sensitive, highest angular resolution survey of Galactic HI emission ever made in the Southern sky. In this paper we outline the survey goals, describe the observations and data analysis, and present the first-stage data release. The data product is a single cube at full resolution, not corrected for stray radiation. Spectra from the survey and other data products are publicly available online.