In this paper, Genetic Algorithms (GA) has been used to achieve optimum use of stream pressure drops when designing a Heat Exchanger Network comprising of Multi-Stream Heat Exchangers (MSHE). The MSHE consists of several block sections with intermediate entry and exit points along the length of unit, determined by the composite curves. Three different approaches have been used for optimization, in all of which the Total Annual Cost (TAC) is considered to be objective function. In first approach, allowable pressure drop of the critical stream in each section is maximized. However, since full utilization of pressure drop of the critical streams does not necessarily lead to uniform block heights, the allowable pressure drops are not fully utilized. In second approach, the drawback in the first approach is removed and a new procedure is presented to achieve uniform block heights as well as full utilization of critical streams’ pressure drops through whole sections. Moreover, fin type is also checked and best fins are selected in order to minimize the objective function. In third approach, a comprehensive optimization is carried out through relaxation of all stream pressure drops, fin types and heat exchanger height and letting all these variables to be optimized simultaneously. It is shown that by applying GA method using the above approaches TAC of the optimized MSHE is improved, compared to those reported in the literature, by 9.5%, 3.9 %, and 10.7 %.