In coal-fired power plants, steam-based air heaters consume high-quality steam and are easily damaged due to water freezing under low ambient temperature conditions. In this paper, we propose an ammonia heat pipe air heater design with hot water in power plants as the heat source, which can eliminate the risk of freezing and save high-quality steam. Based on distributed parameter model and hybrid genetic particle swarm optimization algorithm, an ammonia heat pipe air heater with one-pipe diameter is designed and optimized. The results show that the optimal one-pipe diameter design consumes much less power and owns less weight than the normal empirical design. A new and optimal two-pipe diameter design (i.e., multi-scale design) is further proposed, which drops the power consumption by 10.1% and the weight by 9.4% compared to the optimal one-pipe diameter design. The two optimal designs require different geometrical parameters, especially the pipe diameter(s), the pipe length, the number of heat pipes, and the air side longitudinal pitch. In addition, the two optimal designs provide slightly higher outlet air temperature uniformity than the non-optimal design. Of the three working fluids, i.e., ammonia, methanol, and ethanol, the ammonia heat pipe air heater performs best.