Nitinol, a shape-memory alloy (SMA), is gaining popularity for use in various applications. Machining of these SMAs poses a challenge during conventional machining. Henceforth, in the current study, the wire-electric discharge process has been attempted to machine nickel-titanium (Ni55.8Ti) super-elastic SMA. Furthermore, to render the process viable for industry, a systematic approach comprising response surface methodology (RSM) and a heat-transfer search (HTS) algorithm has been strategized for optimization of process parameters. Pulse-on time, pulse-off time and current were considered as input process parameters, whereas material removal rate (MRR), surface roughness, and micro-hardness were considered as output responses. Residual plots were generated to check the robustness of analysis of variance (ANOVA) results and generated mathematical models. A multi-objective HTS algorithm was executed for generating 2-D and 3-D Pareto optimal points indicating the non-dominant feasible solutions. The proposed combined approach proved to be highly effective in predicting and optimizing the wire electrical discharge machining (WEDM) process parameters. Validation trials were carried out and the error between measured and predicted values was negligible. To ensure the existence of a shape-memory effect even after machining, a differential scanning calorimetry (DSC) test was carried out. The optimized parameters were found to machine the alloy appropriately with the intact shape memory effect.