Refractory metal high-entropy alloys (HEAs) have potential applications as high-temperature materials. For that purpose they should show long-term stability at high temperatures without significant changes in their material properties. However, according to G = H-TS, entropy-stabilized phases will become unstable below a critical temperature leading to phase separation and the formation of characteristic microstructures. This may be welcome or not, in any case it will significantly change the properties of the HEA. Therefore, we studied the atomic ordering and mechanical properties of refractory HEAs (NbTaHfZr, NbTaHfZrTi, NbTaMoW, NbTaMoWV) as a function of annealing time and temperature. We applied temperatures up to eighty percent of the melting temperature and annealing times up to one week. The samples were characterized by X-ray and neutron diffraction, high-resolution electron microscopy and atom probe tomography. The resulting ordering phenomena were further modeled by molecular dynamics calculations.