In the current scenario of manufacturing competitiveness, it is a requirement that new technologies are implemented in order to overcome the challenges of achieving component accuracy, high quality, acceptable surface finish, an increase in the production rate, and enhanced product life with a reduced environmental impact. Along with these conventional challenges, the machining of newly developed smart materials, such as shape memory alloys, also require inputs of intelligent machining strategies. Wire electrical discharge machining (WEDM) is one of the non-traditional machining methods which is independent of the mechanical properties of the work sample and is best suited for machining nitinol shape memory alloys. Nano powder-mixed dielectric fluid for the WEDM process is one of the ways of improving the process capabilities. In the current study, Taguchi’s L16 orthogonal array was implemented to perform the experiments. Current, pulse-on time, pulse-off time, and nano-graphene powder concentration were selected as input process parameters, with material removal rate (MRR) and surface roughness (SR) as output machining characteristics for investigations. The heat transfer search (HTS) algorithm was implemented for obtaining optimal combinations of input parameters for MRR and SR. Single objective optimization showed a maximum MRR of 1.55 mm³/s, and minimum SR of 2.68 µm. The Pareto curve was generated which gives the optimal non-dominant solutions.