Using wavelet analysis and wavelet based empirical orthogonal function analysis(WEOF) on scale-averaged-power, we effectively classified non-stationary and non-linear sea surface temperature fields into spatially coherent regions in the south Atlantic and Indian Oceans that are associated with rainfall variability, in space, time and frequency, in Central Southern Africa (CSA). The dominant signal with an ENSO variance in CSA rainfall was identified as an interdecadal warming and cooling from portions of both the Indian and south Atlantic Oceans. Persistent warming of the Benguela current in south Atlantic ocean and Central Indian ocean coupled with persistent cooling of the south equatorial current and the Agulhas system in Indian ocean have been discovered to result in prolonged decline in rainfall and increased occurrence of droughts in eastern CSA and above average rainfall in western CSA and vice versa. It has also been found that regardless of the factor(s) that lead to warming and cooling, ENSO events are enhanced during warm years and suppressed during the cool years. Using wavelet-based feature vectors in the input spaces of prediction models, excellent prediction skill scores are obtained that depicted the spatial-temporal-frequency variability of rainfall wavelet energy, using both a non-linear prediction model, Genetic Algorithm Neural Network(ANN-GA) and a linear model of Canonical Correlation Analysis(CCA).