Recent experiments show that the chemical composition of body-centered cubic (bcc) refractory high entropy alloys (HEAs) can be tuned to enable transformation-induced plasticity (TRIP), which significantly improves the ductility of these alloys. This calls for an accurate and efficient method to map the structural stability as a function of composition. A key challenge for atomistic simulations is to separate the structural transformation between the bcc and the ω phases from the intrinsic local lattice distortions in such chemically disordered alloys. To solve this issue, we develop a method that utilizes a symmetry analysis to detect differences in the crystal structures. Utilizing this method in combination with ab initio calculations, we demonstrate that local lattice distortions largely affect the phase stability of Ti–Zr–Hf–Ta and Ti–Zr–Nb–Hf–Ta HEAs. If relaxation effects are properly taken into account, the predicted compositions near the bcc–hcp energetic equilibrium are close to the experimental compositions, for which good strength and ductility due to the TRIP effect are observed.