The census of Galactic HII regions is vastly incomplete in the Southern sky. We use the Australia Telescope Compact Array (ATCA) to observe 4-10 GHz radio continuum and hydrogen radio recombination line (RRL) emission from candidate HII regions in the Galactic zone 259 deg < l < 344 deg, |b| < 4 deg. In this first data release, we target the brightest HII region candidates and observe 282 fields in the direction of at least one previously-known or candidate HII region. We detect radio continuum emission and RRL emission in 275 (97.5%) and 258 (91.5%) of these fields, respectively. We catalog the ~7 GHz radio continuum peak flux densities and positions of 80 previously-known and 298 candidate HII regions. After averaging ~18 RRL transitions, we detect 77 RRL velocity components towards 76 previously-known HII regions and 267 RRL velocity components towards 256 HII region candidates. The discovery of RRL emission from these nebulae increases the number of known Galactic HII regions in the surveyed zone by 82%, to 568 nebulae. In the fourth quadrant we discover 50 RRLs with positive velocities, placing those sources outside the Solar circle. Including the pilot survey, the SHRDS has now discovered 295 Galactic HII regions. In the next data release we expect to add ~200 fainter and more distant nebulae.