Fouling problems can seriously affect heat exchanger network (HEN) efficiency and its normal operation. From a fouling threshold model, a higher velocity can effectively mitigate fouling. There are two ways to change the velocity in a heat exchanger. One is to adjust the flow rate distribution in a parallel structure of heat exchangers, the other is to modify the detailed heat exchanger structure. However, there is no research that simultaneously considers both ways to mitigate fouling. Fluid velocity is also an important factor related to heat transfer and pressure drop. But this point is also ignored in most of work. In this paper, a new method is proposed to promote the HEN performance by considering fouling, pressure drop, and heat transfer simultaneously with an overall optimization of velocity. The problem is analyzed in the entire operation time horizon, and it is divided into several time intervals to describe the dynamic nature of the fouling problem. All variables are established in each time interval, and adjacent intervals are linked by the fouling resistance. Simulated annealing (SA) is used in the optimization method. A case study is illustrated to show the capacity of the method. From results, it can be noted that the optimal solution reduces the utility consumption and total annual cost significantly.