Different amounts of Al-5Ti-1B master alloy (TiBAl) were added to the AZ31 magnesium alloy (Mg-3Al-1Zn-0.2Mn) as grain refiner and the resulting microstructure and grain size distributions were studied after extrusion and equal channel angular pressing (ECAP). Results showed that the addition of 0.6% TiBAl had the strongest grain refinement effect, reducing the grain sizes by 54.5 and 48.5% in the extruded and ECAPed conditions, respectively. The observed grain refinement was partly due to the presence of the thermally-stable micron- and submicron-sized particles in the melt which act as nucleation sites during solidification. During the high-temperature extrusion and ECAP processes, dynamic recrystallization (DRX) and grain growth are likely to occur. However, the mentioned particles will help in reducing the grain size by the particle stimulated nucleation (PSN) mechanism. Furthermore, the pinning effect of these particles can oppose grain growth by reducing the grain boundary migration. These two phenomena together with the partitioning of the grains imposed by the severe plastic deformation in the ECAP process have all contributed to the achieved ultrafine-grained structure in the AZ31 alloy.