This article presents a method for the mathematical optimization of the design of heat exchangers including fouling rate modeling for the tube-side. The description of the fouling rate in crude preheat trains of petroleum distillation units is commonly based on threshold models (Ebert-Panchal model and its variants). Our formulation of the design problem employs a mixed-integer linear programing approach; therefore the solution is the global optimum and common nonconvergence drawbacks of mixed-integer nonlinear programming models are totally avoided. Three different examples are employed to compare the proposed approach with an optimization procedure using fixed fouling resistances. The results indicate that in two problems was possible to obtain design solutions associated to smaller heat exchangers. Additionally, three case studies are also explored to discuss how fouling is related to crude types, pressure drop manipulation, and energy integration. (c) 2018 American Institute of Chemical Engineers AIChE J, 64: 2089-2102, 2018