This article discusses the following problem, often encountered when analyzing spatial lattice data. How can one construct a Gaussian Markov random field (GMRF), on a lattice, that reflects well the spatial-covariance properties present either in data or in prior knowledge? The Markov property on a spatial lattice implies spatial dependence expressed conditionally, which allows intuitively appealing site-by-site model building. There are also cases, such as in biological network analysis, where the Markov property has a deep scientific significance. Moreover, the model is often important for computational efficiency of Markov chain Monte Carlo algorithms. In this article, we introduce a new criterion to fit a GMRF to a given Gaussian field, where the Gaussian field is characterized by its spatial covariances. We establish that this criterion is computationally appealing, it can be used on both regular and irregular lattices, and both stationary and nonstationary fields can be fitted. © 2007 Elsevier B.V. All rights reserved.