An output-feedback approach to model predictive control that combines state estimation and control into a single min-max optimization is introduced for discrete-time nonlinear systems. Specifically, a criterion that involves finite forward and backward horizons is minimized with respect to control input variables and is maximized with respect to the unknown initial state as well as disturbance and measurement noise variables. Under appropriate assumptions that encode controllability and observability, we show that the state of the closed-loop remains bounded and that a bound on tracking error can be found for trajectory tracking problems. We also introduce a primal-dual interior-point method that can be used to efficiently solve the min-max optimization problem and show in simulation examples that the method succeeds even for severely nonlinear and non-convex problems.(C) 2016 Elsevier Ltd. All rights reserved.