We demonstrate a novel approach of utilizing a hierarchical microstructure design to improve the mechanical properties of an interstitial carbon doped high-entropy alloy (HEA) by cold rolling and subsequent tempering and annealing. Bimodal microstructures were produced in the tempered specimens consisting of nano-grains (∼50 nm) in the vicinity of shear bands and recovered parent grains (10–35 μm) with pre-existing nano-twins. Upon annealing, partial recrystallization led to trimodal microstructures characterized by small recrystallized grains (<1 μm) associated with shear bands, medium-sized grains (1–6 μm) recrystallized through subgrain rotation or coalescence of parent grains and retained large un-recrystallized grains. To reveal the influence of these hierarchical microstructures on the strength-ductility synergy, the underlying deformation mechanisms and the resultant strain hardening were investigated. A superior yield strength of 1.3 GPa was achieved in the bimodal microstructure, more than two times higher than that of the fully recrystallized microstructure, owing to the presence of nano-sized grains and nano-twins. The ductility was dramatically improved from 14% to 60% in the trimodal structure compared to the bimodal structure due to the appearance of a multi-stage work hardening behavior. This important strain hardening sequence was attributed to the sequential activation of transformation-induced plasticity (TRIP) and twinning-induced plasticity (TWIP) effects as a result of the wide variation in phase stability promoted by the grain size hierarchy. These findings open a broader window for achieving a wide spectrum of mechanical properties for HEAs, making better use of not only compositional variations but also microstructure and phase stability tuning. Display omitted