The moving horizon estimation (MHE) method is an optimization-based technique to estimate the unmeasurable state variables of a nonlinear dynamic system with noise in transition and measurement. One of the advantages of MHE over extended Kalman filter, the alternative approach in this area, is that it considers the physical constraints in its formulation. However, to offer this feature, MHE needs to solve a constrained nonlinear dynamic optimization problem which slows down the estimation process. In this paper, we introduce and employ the Carleman approximation method in the MHE design to accelerate the solution of the optimization problem. The Carleman method approximates the nonlinear system with a polynomial system at a desired accuracy level and recasts it in a bilinear form. By making this approximation, the Karush-Kuhn-Tucker (KKT) matrix required to solve the optimization problem becomes analytically available. Additionally, we perform a stability analysis for the proposed MHE design. As a result of this analysis, we derive a criterion for choosing an order of Carleman approximation procedure that ensures convergence of the scheme. Finally, some simulation results are included that show a significant reduction in the estimation time when the proposed method is employed.