A blind HI survey of the extragalactic sky behind the southern Milky Way has been conducted with the multibeam receiver on the 64-m Parkes radio telescope. The survey covers the Galactic longitude range 212 < l < 36 and Galactic latitudes |b| < 5, and yields 883 galaxies to a recessional velocity of 12,000 km/s. The survey covers the sky within the HIPASS area to greater sensitivity, finding lower HI-mass galaxies at all distances, and probing more completely the large-scale structures at and beyond the distance of the Great Attractor. Fifty-one percent of the HI detections have an optical/NIR counterpart in the literature. A further 27% have new counterparts found in existing, or newly obtained, optical/NIR images. The counterpart rate drops in regions of high foreground stellar crowding and extinction, and for low-HI mass objects. Only 8% of all counterparts have a previous optical redshift measurement. A notable new galaxy is HIZOA J1353-58, a possible companion to the Circinus galaxy. Merging this catalog with the similarly-conducted northern extension (Donley et al. 2005), large-scale structures are delineated, including those within the Puppis and Great Attractor regions, and the Local Void. Several newly-identified structures are revealed here for the first time. Three new galaxy concentrations (NW1, NW2 and NW3) are key in confirming the diagonal crossing of the Great Attractor Wall between the Norma cluster and the CIZA J1324.7-5736 cluster. Further contributors to the general mass overdensity in that area are two new clusters (CW1 and CW2) in the nearer Centaurus Wall, one of which forms part of the striking 180 deg (100/h Mpc) long filament that dominates the southern sky at velocities of ~3000 km/s, and the suggestion of a further Wall at the Great Attractor distance at slightly higher longitudes.