Excellent characteristics of multi-walled carbon nanotubes (MWCNTs), such as higher toughness and stiffness, enlarged strength, and high thermal conductivity, make them an attractive choice to improve surface characteristics and machining performance. In the current study, MWCNTs mixed with dielectric fluid in the wire electrical discharge machining (WEDM) process was used to enhance the machining performance of Nitinol shape memory alloy (SMA). Significance of WEDM machining variables such as current, pulse-on time (Ton), pulse-off time (Toff), and variation in powder concentration of MWCNTs are studied on material removal rate (MRR) and surface roughness (SR). The addition of MWCNTs substantially improves the machining performance by increasing MRR and simultaneously reducing the SR. Improvement in the MRR of 75.42% and SR of 19.15% is achieved with the use of MWCNTs at 1 g/L in comparison to the conventional WEDM process. An advanced parameterless TLBO algorithm is used for simultaneous optimization of multiple responses. An advanced parameterless TLBO algorithm is used to find the optimal solution of multiple responses. Single objective optimization result has yielded maximum MRR of 0.5262 g/min at a current of 5 A, Ton 110 μs, Toff 1 μs and MWCNTs amount of 1 g/L while minimum SR of 1.27 μm at a current of 1 A, Ton 1 μs, Toff 24 μs and MWCNTs amount of 1 g/L. MOTLBO algorithm is used for simultaneous optimization of MRR and SR. Lastly, the surface integrity of machined surfaces using a field emission scanning electron microscope (FESEM) is also studied to evaluate the effect of MWCNTs on recast layer thickness (RLT) and other surface defects. The incorporation of MWCNTs has shown a substantial reduction in RLT and other surface defects such as reduction in globules of debris, melted material deposition, micro-crack-free, and micro-pores-free surfaces.