The Matérn covariance function is a popular choice for modeling dependence in spatial environmental data. Standard Matérn covariance models are, however, often computationally infeasible for large data sets. Recent results for Markov approximations of Gaussian Matérn fields based on Hilbert space approximations are extended using wavelet basis functions. Using a simulation-based study, these Markov approximations are compared with two of the most popular methods for computationally efficient model approximations, covariance tapering and the process convolution method. The methods are compared with respect to their computational properties when used for spatial prediction (kriging), and the results show that, for a given computational cost, the Markov methods have a substantial gain in accuracy compared with the other methods. © 2012 Elsevier B.V. All rights reserved.