A multi-objective optimisation genetic algorithm combining solid solution hardening (SSH) and thermodynamic modelling (CALPHAD) with data mining is used to design high entropy alloys (HEAs). The approach searches for the best compromise between single-phase stability, SSH and density. Thousands of Pareto-optimal base-centred cubic (BCC) HEAs are designed. Al35Cr35Mn8Mo5Ti17 (at.%) is chosen for experimental validation. The alloy was cast and characterised. Its microstructure consists of large grains of a single disordered solid solution displaying a Vickers hardness of 6.45 GPa (658 HV) and a density below 5.5 g/cm3; uniquely combining exceptional hardness with medium density.