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 spatiotemporal evolution of the 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 the temperature in the whole water column, we produce a 3D 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 has 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 specially in those periods with 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 the confidence on 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 time scales (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 also 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.