Moving Horizon Estimation (MHE) is an efficient state estimation method used for nonlinear systems. Since MHE is optimization-based it provides a good framework to handle bounds and constraints when they are required to obtain good state and parameter estimates. Recent research in this area has been directed to develop computationally efficient algorithms for on-line application. However, an open issue in MHE is related to the approximation of the so-called arrival cost and of the parameters associated with it. The arrival cost is very important since it provides a means to incorporate information from the previous measurements to the current state estimate. It is difficult to calculate the true value of the arrival cost; therefore approximation techniques are commonly applied. The conventional method is to use the Extended Kalman Filter (EKF) to approximate the covariance matrix at the beginning of the prediction horizon. This approximation method assumes that the state estimation error is Gaussian. However, when state estimates are bounded or the system is nonlinear, the distribution of the estimation error becomes non-Gaussian. This introduces errors in the arrival cost term which can be mitigated by using longer horizon lengths. This measure, however, significantly increases the size of the nonlinear optimization problem that needs to be solved on-line at each sampling time. Recently, particle filters and related methods have become popular filtering methods that are based on Monte-Carlo simulations. In this way they implement an optimal recursive Bayesian Filter that takes advantage of particle statistics to determine the probability density properties of the states. In the present work, we exploit the features of these sampling-based methods to approximate the arrival cost parameters in the MHE formulation. Also, we show a way to construct an estimate of the log-likelihood of the conditional density of the states using a Particle Filter (PF), which can be used as an approximation of the arrival cost. In both cases, because particles are being propagated through the nonlinear system, the assumption of Gaussianity of the state estimation error can be dropped. Here we developed and tested EKF and eight different types of sample based filters for updating the arrival cost parameters in the weighted 2-norm approach (see Table 1 for the full list). We compare the use of constrained and unconstrained filters, and note that when bounds are required the constrained particle filters give a better approximation of the arrival cost parameters that improve the performance of MHE. Moreover, we also used PF concepts to directly approximate the negative of the log-likelihood of the conditional density using unconstrained and constrained particle filters to update the importance distribution. Also, we show that a benefit of having a better approximation of the arrival cost is that the horizon length required for the MHE can be significantly smaller than when using the conventional MHE approach. This is illustrated by simulation studies done on benchmark problems proposed in the state estimation literature. (C) 2011 Elsevier Ltd. All rights reserved.