Refractory high-entropy alloys (RHEAs) are emerging materials with potential for use under extreme conditions. As a newly developed material system, a comprehensive understanding of their long-term stability under potential service temperatures remains to be established. This study examined a titanium-vanadium-niobium-tantalum alloy, a promising RHEA known for its superior high-temperature strength and room-temperature ductility. Using a combination of advanced analytical microscopies, Calculation of Phase Diagrams (CALPHAD) software, and nanoindentation, we investigated the evolution of its microstructure and mechanical properties upon aging at 700°C. Trace interstitials such as oxygen and nitrogen, initially contributing to solid solution strengthening, promote phase segregation during thermal aging. As a result of the depletion of solute interstitials within the metal matrix, a progressive softening is observed in the alloy as a function of aging time. This study, therefore, underscores the need for a better control of impurities in future development and application of RHEAs.