A new methodology for the computation of the low-temperature part of phase diagrams without recourse to any experimental information is presented. A central element is a procedure for deciding whether formation of crystalline solid solution phases can take place in the chemical system. Via global exploration of the enthalpy landscapes for many different compositions in the system, candidates for ordered stoichiometric and crystalline solid solution phases are identified. Next, their free enthalpies are computed at ab initio level and a low-temperature phase diagram is derived. As examples, the low-temperature phase diagrams for the ternary alkali halides NaCl/LiCl NaBr/LiBr and NaCl/KCl are presented.