The EUSTACE project will give publicly available daily estimates of surface air temperature since 1850 across the globe for the first time by combining surface and satellite data using novel statistical techniques." To fulfil this ambitious mission, a spatio-temporal multiscale statistical Gaussian random field model is constructed, with a hierarchy of spatio-temporal dependence structures, ranging from weather on a daily timescale to climate on a multidecadal timescale. Data from weather stations, ships, and satellites are combined in a hierarchical structure with individual measurement error models, and transformations of the latent random fields to allow joint estimation of current and past temperature fields across the globe. Connections between SPDEs and Markov random fields are used to obtain sparse matrices for the practical computation of point estimates, uncertainty estimates, and posterior samples. The extreme size of the problem necessitates the use of iterative solvers, which requires using the multiscale structure of the model to design an effective preconditioner, leveraging domain specific knowledge, traditional statistical techniques, and modern numerical methods.