Using a combination of artificial intelligence (AI) and density functional theory (DFT), we elucidate the contributions of various entropies, i.e., vibrational, electronic and configurational towards predicting the phase stability of HEAs. We show that the entropy contributions could be quantitatively comparable to the mixing enthalpy; as a result, including various entropy contributions is important for correctly predicting the alloy phase stability. We also show that while the configurational entropy always favors phase stability, the role of vibrational entropy is not predictable. The configurational and vibrational entropies can either compete to destabilize or can collectively contribute to stabilize the solid solutions. As a result, even those systems that have negative mixing enthalpy can show phase instability; conversely, systems with positive mixing enthalpy can have stable phases due to the vibrational entropy contributions. Finally, we discuss our AI database that allows circumventing expensive DFT calculations towards predicting the phase stability of alloys.