Previous studies of wind-blown sand have considered either fully erodible or non-erodible soils, but the transport over sparsely sand-covered soils is still poorly understood. The quantitative modeling of this transport is important for the parameterization of Aeolian processes under limited sediment supply in climate models. Here we show, by means of particle-based numerical simulations, that the Aeolian sand transport rate scales with the wind shear velocity u_∗ as (u_∗-u_∗t).[u_∗²-u_∗t²] where u_∗t is the minimal threshold u_∗ for sustained transport, and the exponent p is a non-linear function of the mobile sand cover thickness. Specifically, we find that the scaling of the Aeolian sand transport rate with u_∗ increases from quadratic to cubic as soil conditions change from fully erodible to rigid. Furthermore, this scaling is affected by the roughness of the non-erodible ground, thus providing constraints for modeling supply limited soils.