The molecular dynamics method was applied to simulate the effects of substrate surface morphology on nano-thermal spraying. The effects of columnar rough surface and smooth surface on cluster flattening, defect evolution of substrate, stress distribution, and the bonding strength between coating and substrate were investigated. The results show that the substrate surface morphology has a significant effect on the bonding strength of thermal spraying. The rough surface increases the actual contact area between the clusters and the matrix, improves the adhesion, causes the anchorage effect at the interface, and thereby enhances the bonding strength. In addition, the substrate surface morphology can change the stress distribution in the interface region. The columnar rough surface on the matrix weakens the stress concentration effect, decreases the critical stress, and reduces the damage to the substrate. Besides, the rough surface hinders the cluster slip and reduces the flattening ratio.