Classical theory of heterogeneous nucleation has been developed with an implied hypothesis of smooth substrate surfaces; however, morphologies of any real substrate surfaces are generally complicated and demonstrate fractal characteristics. In this paper, the wettability between the embryo and the fractal substrate surface was discussed, and heterogeneous nucleation behaviors were theoretically analyzed. The result shows that the roughness factor of a fractal surface varies with the scale of the embryo. As a result, the fractal character of the substrate surface has important effects on heterogeneous nucleation behaviors. It has been shown that the energy barrier for heterogeneous nucleation of a non-wetting phase on a fractal rough surface increases with increasing fractal dimensions, and both the critical nucleus radius and the nucleation energy barrier decrease with increasing fractal dimensions for heterogeneous nucleation of a wetting phase on the fractal rough surface. For a non-wetting system, the critical nucleus radius shows a slight shift with changes of the intrinsic wetting angle, but for a wetting system, the critical nucleus radius shows an obvious change with decreasing intrinsic wetting angle, thus imposes a stronger effect on the heterogeneous nucleation behaviors. Classical theory of heterogeneous nucleation has been developed with an implied hypothesis of smooth substrate surfaces; however, morphologies of any real substrate surfaces are generally complicated and demonstrated fractal characteristics. In this paper, the wettability between the embryo and the fractal substrate surface was discussed, and the heterogeneous nucleation behaviors were theoretically analyzed. The result shows that the roughness factor of a fractal surface varies with the scale of the embryo. As a result, the fractal character of the substrate surface has important effects on heterogeneous nucleation behaviors. It has been shown that the energy barrier for heterogeneous nucleation of a non-wetting phase on a fractal rough surface increases with increasing fractal dimensions, and both the critical nucleus radius and the nucleation energy barrier decrease with increasing fractal dimensions for heterogeneous nucleation of a wetting phase on the fractal rough surface. For a non- wetting system, the critical nucleus radius shows a slight shift with changes of the intrinsic wetting angle, but but for a wetting system, the critical nucleus radius shows an obvious change with decreasing intrinsic wetting angle, thus imposes a stronger effect on the heterogeneous nucleation behaviors.