Multi-principle element alloys have enormous potential, but their exploration suffers from the tremendously large range of configurations. In the last decade such alloys have been designed with a focus on random solid solutions. Here we apply an experimentally verified, combined thermodynamic and first-principles design strategy to reverse the traditional approach and to generate a new type of hcp Al-Hf-Sc-Ti-Zr high entropy alloy with a hitherto unique structure. A phase diagram analysis narrows down the large compositional space to a well-defined set of candidates. First-principles calculations demonstrate the energetic preference of an ordered superstructure over the competing disordered solid solutions. The chief ingredient is the Al concentration, which can be tuned to achieve a D0₁₉ ordering on the hexagonal lattice. The computationally designed D0₁₉ superstructure is experimentally confirmed by transmission electron microscopy and X-ray studies. Our scheme enables the exploration of a new class of high entropy alloys.