Sediment transport along the surface drives geophysical phenomena as diverse as wind erosion and dune formation. The main length-scale controlling the dynamics of sediment erosion and deposition is the saturation length $L_\mathrm{s}$, which characterizes the flux response to a change in transport conditions. Here we derive, for the first time, an expression predicting $L_\mathrm{s}$ as a function of the average sediment velocity under different physical environments. Our expression accounts for both the characteristics of sediment entrainment and the saturation of particle and fluid velocities, and has only two physical parameters which can be estimated directly from independent experiments. We show that our expression is consistent with measurements of $L_\mathrm{s}$ in both aeolian and subaqueous transport regimes over at least five orders of magnitude in the ratio of fluid and particle density, including on Mars.