To improve the permeate flux and to keep the advantage of the high thermal efficiency in air gap membrane distillation (AGMD) for desalination, the optimal design of countercurrent AGMD of the hollow fiber module (AGMD-HF) is proposed. The module is basically composed of hydrophobic porous fiber tubes for feed flow and nonporous tubes for cold flow. The set of mathematical model equations for the entire module is derived from rigorous mass, momentum, and energy balances of both the feed side and the cold side coupled with the simultaneous mass and heat transfer across the membrane. The temperatures across the membrane and along the length of the module are simulated. The sensitivity of the process performance to operating conditions along the fiber length is investigated over a range of temperature and the flow rate. It is found that in the AGMD-HF domain, air/vapor dominates the heat and mass transfer resistances, which are comparable with the available experimental results in the literature. An attempt is then made to adjust the packing density and the surface ratio of the hot porous fibers to the cold nonporous fibers in order to maximize the process performance. Based on the trade-off between productivity and the thermal efficiency under module parameters, optimal design of AGMD-HF using Pareto solutions and the genetic algorithm is finally carried out. The obtained optimal points show that productivity increases considerably at the cost of the higher thermal efficiency with the increase of both packing density of the module and the tube ratio of hot feed fibers to cold fibers, with the latter showing relatively complex effect.