High entropy alloys (HEAs) in the hexagonal close-packed (hcp) phase usually show poor mechanical properties. We demonstrate here, by use of ab initio simulations and detailed experimental investigations, that the mechanical properties can be improved by optimizing the microstructure. In particular we design a dual-phase HEA consisting of a body-centered cubic (bcc) matrix and hcp laths, with nanoprecipitates of the ω phase in the Sc-Ti-Zr-Hf-Re system, by controlling the Re content. This dedicated microstructure reveals, already in the as-cast state, high compressive strength and good ductility of 1910 MPa and 8%, respectively. Our study lifts the hcp-based HEAs onto a competitive, technological level.