Sea surface temperature (SST) is a leading factor impacting coral reefs and causing bleaching events in the Red Sea. A long'term prediction of temperature patterns with an estimate of uncertainty is thus essential for environment man- agement of the Red Sea ecosystem. In this work, we build a data'driven Bayesian structural time series model and show its effectiveness in (1) predicting future SST seasons with a high accuracy, and (2) identifying the main predictive factors of future SST variability among a large number of factors including regional SST and large'scale climate indices. The modelling scheme proposed here applies an efficient hierarchical clustering to identify interconnected subregions that display distinct SST variability over the Red Sea, and a Markov Chain Monte Carlo algorithm to simultaneously select the main predictors while the time series model is being trained. In particular, numerical results indicate that monthly SST can be reliably predicted for the five months ahead.