We map the large-scale sub-structure in the Galactic stellar halo using accurate 3D positions of ~14,000 RR Lyrae reported by the Catalina Sky Survey. In the heliocentric distance range of 10-25 kpc, in the region of the sky approximately bounded by 30{deg} < l < 55{deg} and -45{deg} < b < -25{deg}, there appears to be a strong excess of RRab stars. This overdensity, peaking at 18 kpc, is most likely associated with the so-called Hercules-Aquila Cloud, previously detected using Main Sequence tracers at similar distances in the Sloan Digital Sky Survey data. Our analysis of the period-amplitude distribution of RR Lyrae in this region indicates that the HAC is dominated by the Oosterhoff I type population. By comparing the measured RR Lyrae number density to models of a smooth stellar halo, we estimate the significance of the observed excess and provide an updated estimate of the total luminosity of the Clouds progenitor.