Spatio-temporal hidden Markov models are extremely difficult to estimate because their latent joint distributions are available only in trivial cases. These distributions are usually substituted with pseudo-distributions and this could affect the estimation results, in particular with strong dependence between the latent variables. In this work, we show how inference can be carried out in a Bayesian framework using a Markov chain Monte Carlo (MCMC) algorithm, which eliminates the need to calculate the distribution of the latent variables. This approach is based on the exchange algorithm, an MCMC method which is extensively used for doubly intractable likelihood problems. Since the use of this algorithm is rather uncommon for spatio-temporal models, we propose here an application to this context and provide a simulation study where we compare the pseudo-likelihood MCMC and the proposed algorithm.