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. 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. We raise questions about how to leverage domain specific knowledge and merge traditional statistical techniques with modern numerical methods.