We have studied the low-temperature phase diagrams of the systems MBr-MI (M = Li, Na, K, Rb, or Cs) via global exploration of the enthalpy landscapes for many different compositions, leading to candidates for solid solution-like and ordered crystalline phases. For all of these candidates the free enthalpies are computed at the ab initio level, and the low-temperature phase diagrams of the five chemical systems are derived. We find not only the expected stable solid solution in the rocksalt structure type but also metastable solid solutions based on the CsCl type for the RbBr-RbI and CsCl-CsI systems. Furthermore, additional metastable structure candidates exhibiting ordered crystalline structures exist for several compositions. In the case of the LiBr-LiI system, the metastable solid solution based on the wurtzite type was generated, and the location of the miscibility gap was predicted.