Since the pioneering prediction of surface melting by Michael Faraday, it has been widely accepted that thin water layers, called quasi-liquid layers (QLLs), homogeneously and completely wet ice surfaces. Contrary to this conventional wisdom, here we both theoretically and experimentally demonstrate that QLLs have more than two wetting states and that there is a first-order wetting transition between them. Furthermore, we find that QLLs are born not only under supersaturated conditions, as recently reported, but also at undersaturation, but QLLs are absent at equilibrium. This means that QLLs are a metastable transient state formed through vapor growth and sublimation of ice, casting a serious doubt on the conventional understanding presupposing the spontaneous formation of QLLs in ice-vapor equilibrium. We propose a simple but general physical model that consistently explains these aspects of surface melting and QLLs. Our model shows that a unique interfacial potential solely controls both the wetting and thermodynamic behavior of QLLs.