This paper introduces two new approaches in the thermo-hydraulic design of multi-stream heat exchangers (MSHEs). In both approaches, geometrical aspects of the MSHE (e.g. exchanger dimensions, fin type, etc.) are optimised with a genetic algorithm (GA) using the Total Annual Cost (TAC) as an objective function. The first approach is capable of utilising the maximum allowable stream pressure drops and can result in minimal surface area requirements. In the second approach, all of the pressure drop values are considered as design variables and are therefore subject to optimisation. These approaches have been applied to two case studies taken from literature, and the results are compared to those arising from a currently used design method. In the first case study, application of the new approaches resulted in a smaller TAC than the current approach by 5.77% and 31.86%, respectively, and improvement in the second case was estimated to be 5% and 21.46%, correspondingly. The effect of different fins on an MSHE’s TAC is discussed through application of GAs to the current approach. It is shown that correct selection of fin types reduces the TAC of the two case studies by 21.75% and 8.7%, respectively.