Moving Horizon Estimation (MHE) provides a framework that allows one to incorporate both frequent and infrequent observations easily because it uses a window of past measurements, where the slower ones can be introduced as they become available. Also, MHE allows for the use of constraints on the state estimates, which improves the performance of the estimator. Here we propose the use of a variable structure MHE that can handle multi-rate measurements. Furthermore, we propose a novel strategy for updating the smoothed covariance matrix of the arrival cost based on Nonlinear Programming (NLP) sensitivity. For this we show the relationship that exists between the covariance and the reduced Hessian of the NLP. Moreover, we propose a fast strategy for extracting the reduced Hessian information directly from the linearized optimality conditions used in Interior Point solvers such as IPOPT. The proposed methodology is illustrated using benchmark examples from the literature. (C) 2012 Elsevier Ltd. All rights reserved.