Severe plastic deformation (SPD) is widely considered to be the most efficient process in obtaining ultrafine-grained bulk materials. The aim of this study is to examine the effects of the SPD process on Ni-Fe-Ga ferromagnetic shape memory alloys (FSMA). High-speed high-pressure torsion (HSHPT) was applied in the as-cast state. The exerted key parameters of deformation are described. Microstructural changes, including morphology that were the result of processing, were investigated by optical and scanning electron microscopy. Energy-dispersive X-ray spectroscopy was used to study the two-phase microstructure of the alloys. The influence of deformation on microstructural features, such as martensitic plates, intragranular γ phase precipitates, and grain boundaries’ dependence of the extent of deformation is disclosed by transmission electron microscopy. Moreover, the work brings to light the influence of deformation on the characteristics of martensitic transformation (MT). Vickers hardness measurements were carried out on disks obtained by SPD so as to correlate the hardness with the microstructure. The method represents a feasible alternative to obtain ultrafine-grained bulk Ni-Fe-Ga alloys.