Three grades of titanium alloy Ti (grade 2), Ti-6Al-4V (grade 5) and Ti-5Al-2.5Sn (grade 6) were machined using electric discharge machining after deep and shallow cryogenic treatment. The peak current was observed to be the most significant factor followed by electrode material and pulse-on time. Subsequently, a mathematical model for predicting material removal rate of titanium alloys was developed using dimensional analysis based on the significant process parameters affecting material removal rate and the thermal–physical properties of the titanium alloy. The predicted results obtained from the mathematical model were validated by comparing with the experimental results and were found to be in good agreement with each other. Incremental increase in material removal rate was observed after deep cryogenic treatment due to increase in thermal and electrical conductivity of the material. The model showed that the thermal properties of the material such as thermal conductivity, specific heat and boiling point of materials affect the erosion process in electric discharge machining. Microstructure analysis was carried out using scanning electron microscope, energy-dispersive X-ray spectrometer and X-ray diffraction for selected samples. The migration of different elements and formation of compounds on the machined surface was investigated using energy-dispersive X-ray spectrometer and X-ray diffraction analysis.