An annual cost of heat exchanges materials was taken as the objective function based on the heat exchanger design theory and the material cost calculation method theory of engineering cost in order to optimize the design of media gas-gas heat exchangers (MGGH). The annual cost of heat exchangers materials, specific cost performance of materials, dimensionless cost of materials and other four dimensionless temperature numbers were defined. The MGGH cost model and dimensionless cost model were established. Two methods to solve the two models were given: the analytical method and iterative method. The iterative method was applied to optimize the design parameters of a typical MGGH in a power plant. The materials selection scheme and the optimized design parameters scheme were given. The cost of the MGGH was theoretically reduced by about 5% after optimization. A group of dimensionless relationship graphs of MGGH under several working conditions was obtained. The error between the value obtained by referring to those graphs and the theoretical calculation value was less than 5%.