Although Nickel-Titanium Shape Memory Alloys (NiTi SMAs) are used in a variety of applications due to their shape memory and superelasticity properties, their features of high ductility, temperature sensitivity, and strong work hardening render these materials difficult to machine. The viability of a new approach in improving the machinability through temperature control using chilled air system application was investigated. Differential scanning calorimetry was used to characterise material response to thermal loads. Microstructure phase identification was evaluated with X-ray diffraction. Micro-milling tests were performed using chilled air system and benchmarked to dry cutting and the use of minimum quantity lubricant (MQL). To augment lubrication, chilled air was also applied concurrently with MQL. Results indicated that the application of chilled air reduced cutting temperature and minimised burr height, while their simultaneous application with MQL further improved the machinability. Further investigation was conducted to explore the influence of the ploughing mechanism on machining performance and product quality. The results pointed to higher feed per tooth producing better outcomes. This paper puts forward a new hypothesis that the machinability could be improved by inhibiting or locking in phase transformation through temperature control, and optimising chip thickness, one of the principal parameters of size effect.