Moving Horizon Estimation (MHE) is an efficient optimization-based strategy for state estimation. Despite the attractiveness of this method, its application in industrial settings has been rather limited. This has been mainly due to the difficulty to solve, in real-time, the associated dynamic optimization problems. In this work, a fast MHE algorithm able to overcome this bottleneck is proposed. The strategy exploits recent advances in nonlinear programming algorithms and sensitivity concepts. A detailed analysis of the optimality conditions of MHE problems is presented. As a result, strategies for fast covariance information extraction from general nonlinear programming algorithms are derived. It is shown that highly accurate state estimates can be obtained in large-scale MHE applications with negligible on-line computational costs.