The demand for materials that withstand harsh conditions in high-performance applications has increased drastically in recent years. Due to the predicted outstanding properties of high entropy alloys (HEAs) at elevated temperatures, this class of materials has attracted enormous scientific attention. This paper assesses the phase stability of TiAl-based HEAs, namely TiAlNbV–Mo and TiAlNbV–Mn systems, based on first-principles calculations using Density Functional Theory. We advocate that mixing energies of the HEAs with respect to their possible products offers a suitable way to make predictions about possible decomposition processes. Phase stability is first evaluated at 0 K, followed by the inclusion of the stabilizing effect of the configurational entropy at different temperatures. Additionally, also the effect of vibrational entropy is estimated within the harmonic Debye model. The predicted phase stabilities are discussed in light of existing experimental results showing microstructural evolution before and after heat treatments. Overall, TiAlNbV–Mo, exhibiting a body-centered cucic lattice, has been identified as a kinetically stabilized HEA, whereas TiAlNbV–Mn decomposes into a body-centered cubic phase and the hexagonal Laves phases.