Enhancement of mechanical properties of AZ91 magnesium alloy based on the structural refinement induced by a newly developed Al–5Ti–2B master alloy and subsequent hot working through the extrusion process was studied. The addition of Al–5Ti–2B master alloy resulted in the grain refinement of α-Mg grains mainly due to the inoculating effect of TiB2 particles, where the optimal amount of the grain refiner was found to be ~0.3 wt%. The hot extrusion process led to a remarkable grain refinement and the fracturing and distribution of intermetallics along the extrusion direction. The enhancement of mechanical properties was successfully rationalized based on the grain size, and as a result, Hall-Petch relationships were developed for the yield stress, tensile strength, and hardness. However, the ductility of the extruded alloys was larger than those predicted by the grain size effects alone, which resulted in a superior strength-ductility trade-off compared to the as-cast counterparts. This was related to the disappearance of the grain boundary β-Mg17Al12 phase, closure of casting defects, and formation of a recrystallized and homogeneous microstructure in the extruded alloys.