Energy demand and flue gas emissions, namely carbon dioxide (CO2) associated with the industrial revolution have exhibited a continuous rise. Several approaches were introduced recently to mitigate energy consumption and CO2 emissions by either grass root design or retrofit of existing heat exchanger networks (HEN) in chemical process plants. In this work, a combinatorial approach of path combination is used to generate several options for heat recovery enhancement in HEN. The options are applied to successively shift heat load from HEN utilities using combined utility paths at different heat recovery approach temperature (HRAT) considering exchangers pressure drop. Industrial case study for HEN of the preheat train in crude oil distillation unit from the literature is used to demonstrate the approach. The obtained results have been studied economically using the cost targeting of Pinch Technology. As a result, both external energy usage and CO2 emissions have been reduced from a heater device in HEN by 20% and 17%, respectively, with a payback of less than one year.