This paper introduces a new stepwise approach for the optimal retrofit of heat exchanger networks. At each iteration, the proposed method involves superstructures which embed retrofit alternatives as well as numerical optimization to minimize the project's total annualized cost. In order to reduce calculation times, new algorithms are proposed to thin out superstructures. These are based on thermodynamic criteria, namely on the concept of heat path, and on new graph theoretical results. To carry out the numerical optimization tasks, novel mixed integer nonlinear models are developed. These models support any combination of constant, polynomial and (continuous) piecewise linear enthalpy functions of temperature. Numerical examples are presented for the retrofit of the preheat train of an atmospheric crude unit and for the retrofit of a fluid catalytic cracking plant. The new method is shown to reduce calculation times and total annualized costs reported in the literature. Crown Copyright (C) 2017 Published by Elsevier Ltd. All rights reserved.