An experimental-ab initio approach is applied to investigate solute diffusion in hexagonal high-entropy alloys. The radioisotope 57Co is selected to probe the diffusion behaviour in a series of HCP alloys, from equiatomic binary (HfZr) and ternary (HfTiZr) to quinary Al5Sc20Hf25Ti25Zr25 at.% and Al15Sc10Hf25Ti25Zr25 at.% high-entropy alloys. Diffusion of Co in the present alloys is found to be strongly anisotropic and exceptionally fast (by 5 to 10 orders of magnitude faster than self-diffusion) which can be explained in terms of a dissociative diffusion mechanism. The origin of ultra-fast diffusion of Co in the given HCP high-entropy alloys and the impact of the multi-element environment on the interstitial positions are analyzed in the framework of ab initio computations. Our results show that solute diffusion can be used as a tool to probe potential short range order in HCP multi-principal element alloys on very short time scales with respect to the jump rates of matrix atoms. © 2020 Acta Materialia Inc.