We have studied a nanocrystalline AlCrCuFeNiZn high-entropy alloy synthesized by ball milling followed by hot compaction at 600 C for 15 min at 650 MPa. X-ray diffraction reveals that the mechanically alloyed powder consists of a solid-solution body-centered cubic (bcc) matrix containing 12 vol.% face-centered cubic (fcc) phase. After hot compaction, it consists of 60 vol.% bcc and 40 vol.% fcc. Composition analysis by atom probe tomography shows that the material is not a homogeneous fcc-bcc solid solution but instead a composite of bcc structured Ni-Al-, Cr-Fe- and Fe-Cr-based regions and of fcc Cu-Zn-based regions. The Cu-Zn-rich phase has 30 at.% Zn α-brass composition. It segregates predominantly along grain boundaries thereby stabilizing the nanocrystalline microstructure and preventing grain growth. The Cr- and Fe-rich bcc regions were presumably formed by spinodal decomposition of a Cr-Fe phase that was inherited from the hot compacted state. The Ni-Al phase remains stable even after hot compaction and forms the dominant bcc matrix phase. The crystallite sizes are in the range of 20-30 nm as determined by transmission electron microscopy. The hot compacted alloy exhibited very high hardness of 870 ± 10 HV. The results reveal that phase decomposition rather than homogeneous mixing is prevalent in this alloy. Hence, our current observations fail to justify the present high-entropy alloy design concept. Therefore, a strategy guided more by structure and thermodynamics for designing high-entropy alloys is encouraged as a pathway towards exploiting the solid-solution and stability idea inherent in this concept. © 2013 Acta Materialia Inc. Published by Elsevier Ltd. All rights reserved.