Our work highlights the complex interplay between entropy and internal energy in the formation of metal-water interfaces. We have shown that while the water adsorption energy is a good descriptor of the internal energy part of the interface formation, it alone cannot satisfactorily explain the interfacial thermodynamics due to the notable and metal-dependent entropic contributions of water at room temperature. Our results show that the metal-water interface formation is entropically most favorable for surfaces with a moderately organized water structure and a high number of translational degrees of freedom at low frequencies. Combined together, the most favorable surface solvation is observed for Pd, which forms a moderately strong bond with water but still has a fairly flexible interfacial water layer.