Cryogenic air separation units constitute an integral part of many industrial processes and next generation power plants. These units are characterized by fluctuating operating conditions to respond to changing product demands. The dynamics of these transitions are highly nonlinear and energy-intensive. Consequently, nonlinear model predictive control (NMPC) based on rigorous dynamic models is essential for high performance in these applications. Currently, the implementation of NMPC controllers is limited by the computational complexity of the associated on-line optimization problems. In this work, we make use of the so-called advanced step NMPC controller to overcome these limitations. We demonstrate that this sensitivity-based strategy reduces the on-line computational time to just a single CPU second, while incorporating a highly detailed dynamic air separation unit model. Finally, we demonstrate that the controller can handle nonlinear dynamics over a wide range of operating conditions. (C) 2008 Elsevier Ltd. All rights reserved.