High purity distillation columns are critical unit operations in cryogenic air separation plants that supply purified gases to a number of industries. We have developed a nonlinear model predictive control (NMPC) strategy based on the assumption of full-state feedback for a prototypical cryogenic distillation column to allow effective operation over a wide range of plant production rates. The controller design was based on a reduced-order compartmental model derived from detailed mass and energy balances by exploiting time-scale separations. Temporal discretization of the compartmental model produced a very large set of nonlinear differential and algebraic equations with advantageous sparsity properties, enabling online solution of the NMPC problem. The synergistic combination of several real-time implementation techniques were found to be essential for further reducing computation time and allowing reliable solution within the 2-min controller sampling interval. Closed-loop simulation studies demonstrated the performance advantages of NMPC compared to linear model predictive control technology currently used in the air separation industry.