New environmental legislation on emission and fuel efficiency targets increasingly requires good transient engine performance and this in turn means that the previously acceptable static engine calibration and control methodologies based on steady-state testing must be re-placed by dynamical optimization using dynamical models. Although many advances have been made in predictive models for internal combustion engines, the phenomena involved are so many, complex and nonlinear that dynamical black-box models typically employing neural network structures must be determined from system identification through experimental testing. Such identified dynamical models are required to provide high accuracy multiple step-ahead predictions of emissions but must accordingly also be compactly implementable for speed and memory to allow for the required large scale optimization involving possibly many thousands of iterations.This paper presents a novel methodology of using black box modeling techniques to build compact efficiently implementable nonlinear dynamic engine models with high predictive accuracy in the form of Neural Network and polynomial equations. The black box models obtained are shown to be efficient for state-of-the-art model-based fuel economy dynamical optimization with emission constraints. The effectiveness and relative efficiency of using polynomial models V.S. full Neural Network (NN) models in the fuel economy optimization are demonstrated. A novel multi-step ahead (simulation) output based parameter estimation method is proposed to improve the predictive accuracy of polynomial models.