Refractory high-entropy alloys (RHEAs) have recently attracted much attention, primarily due to their mechanical properties at elevated temperatures. However, the equilibrium phase-stability of these alloy systems is not well established. The present investigation focuses on the phase stability of Al0.5NbTa0.8Ti1.5V0.2Zr RHEA at temperatures ranging from 600 to 1200 °C. The detailed phase characterization involves coupling of scanning electron microscopy, transmission electron microscopy, and atom probe tomography. The stable phases present at these temperatures are (i) 1200 °C—body-centered cubic (BCC) matrix with nano-B2 precipitates; (ii) 1000 °C and 800 °C—a BCC matrix phase with Al–Zr rich hexagonal closed packed intermetallic precipitates and, (iii) 600 °C—a BCC + B2 microstructure, comprising a continuous BCC matrix with discrete B2 precipitates. These results highlight the substantial changes in phase stability as a function of temperature in RHEAs, and high-entropy alloys in general, and also the importance of accounting for these changes especially while designing alloys for high temperature applications.