Understanding the ice adhesion mechanism is vital for efficient anti-icing. However, previous studies focused on the adhesion of already sintered ice-solid contacts. Here, we study the adhesion mechanism between preformed ice and solid surfaces. In particular, we investigate the initial stages of ice adhesion. We find that capillary bridges formed by the quasi-liquid layer on the ice surface enhance ice adhesion. The adhesion force showed a maximum around −2 °C. Our model indicates that the nano-scaled curvature of the capillary bridge gives rise to strong adhesion forces in the temperatures between −5 and 0 °C. The capillary bridge expands and consolidates over time, causing an increase of adhesion force. These findings provide new physical insights into the ice adhesion mechanism with strong implications to the development of water-repellent superhydrophobic coatings for efficient anti-icing of solid surfaces.