The contact force–indentation-depth (P–h) measurements in adhesive contact experiments, such as atomic force microscopy, display hysteresis. In some cases, the amount of hysteretic energy loss is found to depend on the maximum indentation-depth. This depth-dependent hysteresis (DDH) is not explained by classical contact theories, such as Johnson–Kendall–Roberts and Derjaguin–Muller–Toporov, and is often attributed to surface moisture, material viscoelasticity, and plasticity. We present molecular statics simulations that are devoid of these mechanisms, yet still capture DDH. In our simulations, DDH is due to a series of surface mechanical instabilities. Surface features, such as depressions or protrusions, can temporarily arrest the growth or recession of the contact area. With a sufficiently large change of indentation-depth, the contact area grows or recedes abruptly by a finite amount and dissipates energy. This is similar to the pull-in and pull-off instabilities in classical contact theories, except that in this case the number of instabilities depends on the roughness of the contact surface. Larger maximum indentation-depths result in more surface features participating in the load–unload process, resulting in larger hysteretic energy losses. This mechanism is similar to the one recently proposed by one of the authors using a continuum mechanics-based model. However, that model predicts that the hysteretic energy loss always increases with roughness, whereas experimentally it is found that the hysteretic energy loss initially increases but then later decreases with roughness. Our simulations capture this non-monotonic dependence of hysteretic energy loss on roughness.