Much of the surface of Mars is covered by dunes, ripples, and other features formed by the blowing of sand by wind, known as saltation. In addition, saltation loads the atmosphere with dust aerosols, which dominate the Martian climate. We show here that saltation can be maintained on Mars by wind speeds an order of magnitude less than required to initiate it. We further show that this hysteresis effect causes saltation to occur for much lower wind speeds than previously thought. These findings have important implications for the formation of dust storms, sand dunes, and ripples on Mars.