The wind-driven saltation of granular material plays a key role in various geophysical processes on Earth, Mars, Venus, and Titan. Although interparticle cohesion is known to limit the number of grains lifted from the surface through aerodynamic entrainment and granular splash, the role of cohesion in the development of saltation from onset to steady state is still poorly understood. Using a numerical model based on the discrete element method, we show that saltation over cohesive beds sustains itself at wind speeds 1 order of magnitude smaller than those necessary to initiate it, giving rise to hysteresis in which the occurrence of transport depends on the history of the wind. Our results further suggest that saltation over cohesive beds requires much longer distances to saturate, thereby increasing the size of the smallest stable bed forms. These findings have implications for dune formation, dust emission, and snow sublimation over cohesive beds.