Thermal spray coatings are widely used in many applications, and the adhesion effect at the coating/substrate interface plays an important role during the service life. The thermal spraying coating and substrate is primarily combined by a mechanical seizure effect. In this work, a strategy to generate interfacial metallurgical bonding is proposed. Plasma spraying with wire feeding was adopted to increase the size of sprayed particles, and metallurgical bonding was clearly formed between deposited particles and the substrate (304 stainless-steel and 7075 aluminum alloy). Interface reaction can be found at both NiAl/7075 and NiAl/304 interfaces. Typical Al-Al3Ni eutectic phase with higher microhardness was formed at NiAl/7075 interface. The adhesive strength of the coatings was significantly improved to 82.67 ± 3.96 MPa and 64.45 ± 2.84 MPa, respectively, for NiAl coating on 304 and 7075 substrates through tensile adhesion tests (TAT) without surface roughening pretreatment. This technique shows a promising aspect of the application of thermal spray coatings.