Solid solutions, structurally ordered but compositionally disordered mixtures, can form for salts, metals, and even organic compounds. The NaCl-KCl system forms a solid solution at all compositions between 657 °C and 505 °C. Below a critical temperature of 505 °C, the system exhibits a miscibility gap with coexisting Na-rich and K-rich rocksalt phases. We calculate the phase diagram in this region using the semi-grand canonical Widom method, which averages over virtual particle transmutations. We verify our results by comparison with free energies calculated from thermodynamic integration and extrapolate the location of the critical point. Our calculations reproduce the experimental phase diagram remarkably well and illustrate how solid-solid equilibria and chemical potentials, including those at metastable conditions, can be computed for materials that form solid solutions.