Although several methods have been proposed in design of multi-stream heat exchangers, but they often apply for constant physical properties. In this research, a new method is presented using the variation of physical properties with temperature as well as optimum pressure drops. Having indicated the dependency of specific heat capacity, viscosity, density and thermal conductivity on temperature variation, a set of temperature correction factors is defined for each stream. Calculating the correction factors for all streams will lead in finding an optimum DTmin in targeting stage as well as a reliable design based on effective pressure drops, which will guarantee the accuracy of results. Moreover, the optimum pressure drops are used by the optimum selection of fins for each stream in which the total annual cost of exchanger is minimized using genetic algorithm. Having applied the temperature correction factors in design of a multi-stream heat exchanger as case study, the results showed a 27.3% and 13.5% reduction in exchanger volume and total annual cost, respectively, compared to those calculated based on constant physical properties. Also, by optimization of fin types using the genetic algorithm, the results showed a 4.28% and 4.92% reduction in volume and total annual cost, respectively.