Saltation, the motion of sand grains in a sequence of ballistic trajectories close to the ground, is a major factor for surface erosion, dune formation, and triggering of dust storms on Mars. Although this mode of sand transport has been matter of research for decades through both simulations and wind tunnel experiments under Earth and Mars conditions, it has not been possible to provide accurate measurements of particle trajectories in fully developed turbulent flow. Here we calculate the motion of saltating grains by directly solving the turbulent wind field and its interaction with the particles. Our calculations show that the minimal wind velocity required to sustain saltation on Mars may be surprisingly lower than the aerodynamic minimal threshold measurable in wind tunnels. Indeed, Mars grains saltate in 100 times higher and longer trajectories and reach 5-10 times higher velocities than Earth grains do. On the basis of our results, we arrive at general expressions that can be applied to calculate the length and height of saltation trajectories and the flux of grains in saltation under various physical conditions, when the wind velocity is close to the minimal threshold for saltation.