The retrofit design of heat exchanger networks (HENs) presents a more difficult challenge to mathematical programming methods even than grassroots design. Pinch technology methods based on thermodynamics take no account in their pure form of the benefit to be gained by using existing area in a HEN retrofit or of repiping costs which may be significant. A novel approach to the retrofit problem using Constraint Logic Programming (CLP) is described here. It employs a set of heuristics derived from an interactive retrofit method published earlier (Lakshmanan and Banares-Alcantara, 1996), and uses CLP to efficiently prune out unattractive solutions. In most of the case studies on which the program was tested, the solutions were superior to others reported in the literature, although there is no guarantee of optimality. The approach also generates a set of solutions rather than just one, which may make the automatically generated retrofit proposals more acceptable in industry.