State estimators for nonlinear systems are derived based on polynomial approximations obtained with a multi-dimensional interpolation formula. It is shown that under certain assumptions the estimators perform better than estimators based on Taylor approximations. Nevertheless, the implementation is significantly simpler as no derivatives are required. Thus, it is believed that the new state estimators can replace well-known estimators, such as the extended Kalman filter (EKF) and its higher-order relatives, in most practical applications.