We present the first results from a pilot study to search for distant radio galaxies in the southern hemisphere (delta < -32). Within a 360 deg^2 region of sky, we define a sample of 76 ultra-steep spectrum (USS) radio sources from the 843 MHz Sydney University Molonglo Sky Survey (SUMSS) and 1.4 GHz NRAO VLA Sky Survey (NVSS) radio surveys with alpha_843^1400 < -1.3 and S_1400 > 15 mJy. We observed 71 sources without bright optical or near-infrared counterparts at 1.385 GHz with the ATCA, providing ~5" resolution images and sub-arcsec positional accuracy. To identify their host galaxies, we obtained near-IR K-band images with IRIS2 at the AAT and SofI at the NTT. We identify 92% of the USS sources down to K~20.5. The SUMSS-NVSS USS sources have a surface density more than 4 times higher than USS sources selected at lower frequencies. This is due to the higher effective selection frequency, and the well-matched resolutions of both surveys constructed using the same source fitting algorithm. The scattering of alpha >-1.3 sources into the USS sample due to spectral index uncertainties can account for only 35% of the observed USS sources. Since our sample appears to contain a similar fraction of very distant (z>3) galaxies, selecting USS sources from SUMSS-NVSS should allow us to identify large numbers of massive galaxies at high redshift.