Based on real-time identification and using the concept of NARX (Nonlinear AutoRegressive with exogenous inputs) models, a new adaptive nonlinear predictive controller (ANPC) design is proposed. NARX models represent a natural way to describe the input-output relationship of severely nonlinear systems. From an initial batch of input-output data, a parsimonious NARX model is obtained using the Modified Gram-Schmidt (MGS) orthogonalization algorithm. Following this initial off-line identification and model reduction procedure, the control loop is closed. The ANPC directly uses the obtained structure and initial parameter estimates, which are updated each time step using recursive identification. The controller is designed similar to a typical linear predictive controller based on solving a nonlinear programming (NLP) problem. This paper shows how to solve this NLP problem on-line without the knowledge of the NARX model structure. The design is given for the multi-input multi-output (MIMO) case.