Most theoretical approaches to retrofitting industrial heat exchanger networks (HENs), besides presenting some impractical modifications (such as relocating and modifying exchangers), often fail to account for the temperature dependency of physical properties and the phase changes of streams within the exchangers during the modification process. Consequently, this research presents a three-step method to address these shortcomings. In this method, the process exchangers are first removed from the initial network. Subsequently, the retrofitting of the remaining network, which includes only utility exchangers, is modified using a novel hybrid approach that combines a genetic algorithm (GA) with a mathematical optimization method (MOM), enhanced by simulator software (SS). The GA handles structural variables, while continuous variables are optimized by the MOM. This model includes both linear and integer programming models with a correction procedure and is capable of considering all retrofit strategies. To achieve realistic results, SS is employed to account for the effects of pressure and temperature on physical properties and to perform phase change calculations. Two case studies were conducted to evaluate the proposed method. The first one focuses on examining the high performance of the GA-MOM model in providing all modification suggestions. The second, which involves HEN retrofitting of a real industrial plant, demonstrates the effectiveness of the proposed three-step method (i.e., GA-MOM-SS).