Soft solids are sticky. They attract each other and spontaneously form a large area of contact. Their force of attraction is higher when separating than when forming contact, a phenomenon known as adhesion hysteresis. The common explanation for this hysteresis is viscoelastic energy dissipation or contact aging. Here, we use experiments and simulations to show that it emerges even for perfectly elastic solids. Pinning by surface roughness triggers the stick-slip motion of the contact line, dissipating energy. We derive a simple and general parameter-free equation that quantitatively describes contact formation in the presence of roughness. Our results highlight the crucial role of surface roughness and present a fundamental shift in our understanding of soft adhesion.