Abstract. The Red Sea holds one of the most diverse marine ecosystems in the world, although fragile and vulnerable to ocean warming. Several studies have analysed the spatio-temporal evolution of temperature in the Red Sea using satellite data, thus focusing only on the surface layer and covering the last ∼30 years. To better understand the long-term variability and trends of temperature in the whole water column, we produce a 3-D gridded temperature product (TEMPERSEA) for the period 1958–2017, based on a large number of in situ observations, covering the Red Sea and the Gulf of Aden. After a specific quality control, a mapping algorithm based on optimal interpolation have been applied to homogenize the data. Also, an estimate of the uncertainties of the product has been generated. The calibration of the algorithm and the uncertainty computation has been done through sensitivity experiments based on synthetic data from a realistic numerical simulation. TEMPERSEA has been compared to satellite observations of sea surface temperature for the period 1981–2017, showing good agreement especially in those periods when a reasonable number of observations were available. Also, very good agreement has been found between air temperatures and reconstructed sea temperatures in the upper 100 m for the whole period 1958–2017, enhancing confidence in the quality of the product. The product has been used to characterize the spatio-temporal variability of the temperature field in the Red Sea and the Gulf of Aden at different timescales (seasonal, interannual and multidecadal). Clear differences have been found between the two regions suggesting that the Red Sea variability is mainly driven by air–sea interactions, while in the Gulf of Aden the lateral advection of water plays a relevant role. Regarding long-term evolution, our results show only positive trends above 40 m depth, with maximum trends of 0.045 + 0.016 ∘C decade−1 at 15 m, and the largest negative trends at 125 m (-0.072+0.011 ∘C decade−1). Multidecadal variations have a strong impact on the trend computation and restricting them to the last 30–40 years of data can bias high the trend estimates.