The effect of a substrate on the heterogeneous two-dimensional (2D) nucleation of colloidal crystals has been investigated. Nucleation rates, J, of 2D colloidal crystals on uncoated cover glass, Pt-coated cover glass, and Au-coated cover glass are measured. Among the three substrates, the J of the uncoated cover glass is found to be the largest, while it is smallest for the Pt-coated cover glass under the same supersaturation conditions. The interfacial free energy change, ?σ, is obtained from the nucleation rate based on classical nucleation theory (CNT), indicating that uncoated cover glass possesses the smallest ?σ, while it is largest for the Pt-coated cover glass. Since ?σ originates from the bond energy in atomic crystals, we deduce that it is related to the interaction between colloidal particles and the substrate in a colloidal system. The interactions between a colloidal particle (polystyrene) and each substrate are determined with surface force measurements using atomic force microscopy (AFM). The results show that the adhesive force, which predominantly consists of the van der Waals force, between particles and uncoated cover glass, is the weakest, while that for the Pt-coated cover glass is the strongest. A larger attractive interaction between the colloidal particles and the substrate yields a higher ?σ, and thus a smaller J. The interaction between particles and substrate has a great influence on the heterogeneous nucleation rate of colloidal crystals.