Heterogeneous nanostructured metals are emerging strategies for achieving both high strength and ductility, which are particularly attractive for high entropy alloys (HEAs) to combine the synergistic enhancements from multielement composition, grain boundaries, and heterogeneity effects. However, the construction of heterogeneous nanostructured HEAs remains elusive and can involve delicate processes that are not practically scalable. Herein we report using composition design (i.e., enthalpy engineering) to create hierarchical, nanostructured HEAs as demonstrated by adding Ni into FeCrCoAlTi0.5 HEA. The strong enthalpic interaction between (Ni,Co) and (Al,Ti) pairs in FeCrCoAlTi0.5Nix (x = 0.5–1.5) induced phase partitions into B2 (ordered phase, hard) matrix and A2 (disordered phase, soft) precipitates, resulting in a hierarchical structure of B2 grains and sub-grains of near-coherent A2 nanodomains (~ 12.5 nm) divided by A2 interdendritic regions. As a result, the FeCrCoAlTi0.5Ni1.5 HEA with this unique hierarchical nanostructure exhibits the best combination of strength and plasticity, i.e., a 2-fold increase in compressive strength (2.60 GPa) and significant enhancement of plastic strain (15.8%) as compared with the original FeCrCoAlTi0.5 HEA. Enthalpy analysis and simulation study reveal the phase partition process during cooling induced by an enthalpy-driven order-disorder transition while the order parameters illustrate the strong ordering in (Ni,Co)(Al,Ti)-rich B2 phase and high entropy mixing in less interactive FeCrCo-rich A2 phase. Our work therefore provides a strategy for hierarchical nanostructured HEA formation by composition design considering enthalpy and entropy interplay.