In this article, a multi-objective exergy-based optimization through a genetic algorithm method is conducted to study and improve the performance of shell-and-tube type heat recovery heat exchangers, by considering two key parameters, such as exergy efficiency and cost. The total cost includes the capital investment for equipment (heat exchanger surface area) and operating cost (energy expenditures related to pumping). The design parameters of this study are chosen as tube arrangement, tube diameters, tube pitch ratio, tube length, tube number, baffle spacing ratio, and baffle cut ratio. In addition, for optimal design of a shell-and-tube heat exchanger, the epsilon - NTU method and Bell-Delaware procedure are followed to estimate its pressure drop and heat transfer coefficient. A fast and elitist nondominated sorting genetic algorithm (NSGA-II) with continuous and discrete variables is applied to obtain maximum exergy efficiency with minimum exergy destruction and minimum total cost as two objective functions. The results of optimal designs are a set of multiple optimum solutions, called "Pareto optimal solutions." The results clearly reveal the conflict between two objective functions and also any geometrical changes that increase the exergy efficiency (decrease the exergy destruction) lead to an increase in the total cost and vice versa. In addition, optimization of the heat exchanger based on exergy analysis revealed that irreversibility like pressure drop and high temperature differences between the hot and cold stream play a key role in exergy destruction. Therefore, increasing the component efficiency of a shell-and-tube heat exchanger increases the cost of heat exchanger. Finally, the sensitivity analysis of change in optimum exergy efficiency, exergy destruction, and total cost with change in decision variables of the shell-and-tube heat exchanger is also performed.