We have developed a method to accurately and efficiently determine the vibrational free energy as a function of temperature and volume for substitutional alloys from first principles. Taking Ti$_{1-x}$Al$_x$N alloy as a model system, we calculate the isostructural phase diagram by finding the global minimum of the free energy, corresponding to the true equilibrium state of the system. We demonstrate that the anharmonic contribution and temperature dependence of the mixing enthalpy have a decisive impact on the calculated phase diagram of a Ti$_{1-x}$Al$_x$N alloy, lowering the maximum temperature for the miscibility gap from 6560 K to 2860 K. Our local chemical composition measurements on thermally aged Ti$_{0.5}$Al$_{0.5}$N alloys agree with the calculated phase diagram.