Climate change is typically modelled using sophisticated mathematical models (climate models) of physical processes that range in temporal and spatial scales. Multi-model ensemble means of climate models show better correlation with the observations than any of the models separately. Currently, an open research question is how climate models can be combined to create an ensemble mean in an optimal way. We present a novel stochastic approach based on Markov chains to estimate model weights in order to obtain ensemble means and uncertainty estimations on spatially explicit climate data. The method was compared to existing alternatives by measuring its performance in cross-validation and model-as-truth experiments on a diverse set of public climate datasets. The Markov chain method showed improved performance over those methods when measured by a set of metrics: root mean squared error, climatological monthly root mean squared error, monthly trend bias, interannual variability, uncertainty error etc. The results of this comparative analysis should serve to motivate further studies in applications of Markov chain and other nonlinear methods that address the issues of finding optimal model weight for constructing weighted ensemble means and uncertainty estimations.