This paper develops an extended ellipsoidal outer-bounding set-membership estimation (EEOB-SME) algorithm with high accuracy and efficiency for nonlinear discrete-time systems under unknown-but-bounded (UBB) disturbances. The EEOB-SME linearizes the first-order terms about the current state estimations and bounds the linearization errors by ellipsoids using interval analysis for nonlinear equations of process and measurement equations, respectively. It has been demonstrated that the EEOB-SME algorithm is stable and the estimation errors of the EEOB-SME are bounded when the nonlinear system is observable. The EEOB-SME decreases the computation load and the feasible sets of EEOB-SME contain more true states. The efficiency of the EEOB-SME algorithm has been shown by a numerical simulation under UBB disturbances.