We present a deep photometric (B- and R-band) catalog and an associated spectroscopic redshift survey conducted in the vicinity of the Hubble Deep Field South. The spectroscopy yields 53 extragalactic redshifts in the range 0<z<1.4 substantially increasing the body of spectroscopic work in this field to over 200 objects. The targets are selected from deep AAT prime focus images complete to R<24 and spectroscopy is 50% complete at R=23. There is now strong evidence for a rich cluster at z\simeq 0.58 flanking the WFPC2 field which is consistent with a known absorber of the bright QSO in this field. We find that photometric redshifts of z<1 galaxies in this field based on HST data are accurate to \sigma_z/(1+z)=0.03 (albeit with small number statistics). The observations were carried out as a community service for Hubble Deep Field science, to demonstrate the first use of the `nod & shuffle' technique with a classical multi-object spectrograph and to test the use of `microslits' for ultra-high multiplex observations along with a new VPH grism and deep-depletion CCD. The reduction of this new type of data is also described.