The metal-support interaction plays a critical role in heterogeneous catalysis. Under reducing conditions, oxidic supports may interact with supported metal particles, by either forming an oxide overlayer or an alloy. The structure of both the support and the nanoparticle, as well as of the interface itself, changes in response to varying environmental conditions. Here, we present a fullyab initioapproach to predict the structures and energetics of such systems for a range of transition metals (Me = Cu, Ru, Pd, Ag, Rh, Os, Ir, Pt, Au) supported on titania surfaces as a function of gas atmosphere composition. The competing formation of a monolayer comprising fully oxidized titania (TiO2), its reduced forms (Ti2O3, TiO), and the Ti-Me surface alloy, is investigated. The stability of each of these phases is found to be very sensitive to the environmental conditions and the supported metal. Encapsulation of metal, also known as classical strong metal-support interaction (SMSI), was predicted by thermodynamic driving force analysis. We show that a simple parameter, the Ti-Me alloy formation energy, is a good descriptor for the strength of the interaction between metal substrates and reduced titania monolayers and has predictive power towards the conditions under which an overlayer is stable. The presented thermochemical data and phase diagram analysis can be used to identify the structure and stability of supported metal catalysts under realistic conditions.