Most literature on the synthesis of heat exchanger networks via mathematical programming methods has dealt with phase changes by assuming nearly isothermal conditions. Many multicomponent phase changes of practical interest (e.g., those in sub-ambient processes) occur over ranges of temperatures and exhibit nonlinear temperature-enthalpy relations (T-H curve). In such cases, isothermal approximations may lead to inferior or unacceptable networks. In this article, we propose a mixed-integer nonlinear programming formulation and a solution algorithm to incorporate nonisothermal phase changes in heat exchanger network synthesis. We approximate the nonlinear T-H curves via empirical cubic correlations, and propose a procedure to ensure minimum temperature approach at all points in the exchangers. Our approach successfully solves two industry examples and shows promise for significant cost reductions when compared with existing processes. (C) 2009 American Institute of Chemical Engineers AIChE J, 56: 930-945, 2010