We present the results of a deep, wide-area variability survey in the Southern hemisphere, the first of its kind. As part of the Catalina Sky Surveys, the Siding Spring Survey (SSS) has covered $14,800$ square degrees in the declination range of $-75^{circ}leqdeltaleq-15^{circ}$. To mine the enormous SSS dataset efficiently we have developed two algorithms: Automatic Period Selection (APS) and Automatic Fourier Decomposition (AFD), which aim to sharpen the period estimation and produce robust lightcurve models. Armed with the APS and AFD outputs we classify $10,540$ ab-type RR Lyrae (RRab) stars ($sim$90% of which are new) across the Southern sky. As well as the positional information we supply photometric metallicities, and unreddened distances. For the RRab stars in the halo, a study of the photometric metallicity distribution reveals a nearly Gaussian shape with a mean metallicity of ${rm [Fe/H]}=-1.4$ dex and a dispersion of $0.3$ dex. A spatial study of the RRab metallicities shows no significant radial gradient in the first $sim7$ kpc from the Galaxy center. However, further out, a small negative gradient is clearly present. This is complemented by a very obvious correlation of the mean RR Lyrae metallicity with distance above the Galactic plane, $z$. We have also carried out an initial substructure search using the discovered RRab, and present the properties of the candidates with significance greater than $2 sigma$. Most prominent among these is a southern extension of the Sagittarius dwarf galaxy’s stream system, reaching down to declinations $sim -40deg$.