We calculate the transition temperature versus concentration (Tc vs c) phase diagrams of several phase-segregating alloys [fcc Ca-Sr, Au-Pt, and Rh-(Pd,Cu,Ag,Au)] using a multiscale method combining first-principles calculations and Monte Carlo via the cluster expansion (CE). We study Pd-Rh, with its well-known high-T miscibility gap, to verify the method’s reliability. We predict that Ca-Sr segregates at low temperatures. We then show that a rapid estimate of Tc is obtained from enthalpies analytically derived from a CE, and, using thermodynamic integration, we determine under what circumstances this mean-field estimate is accurate compared to Monte Carlo results. Also, we discuss how an electronegativity difference of the alloying elements quickly assess when vibrational entropy effects should be included in the estimate of Tc.