When Voyager 2 imaged the surface of Neptune's moon Triton in 1989, it revealed the occurrence of surface streaks that are possibly of aeolian origin (i.e., wind-formed) (1,2). Likewise, New Horizons imaged surface features that have been tentatively interpreted as possible wind streaks when it passed Pluto in 2015 (3). Moreover, Rosetta imaged what looked like aeolian ripples and dunes on the comet 67P/Churyumov-Gerasimenko (67P) in 2014 (4,5). However, whether these surface features formed due to aeolian sand transport remains a mystery (2-5) because the atmospheres on these planetary bodies are extremely thin. In fact, it has been estimated that average 1m winds of more than 500km/h are required to lift sand from the surface on Triton and Pluto (6), where winds are weaker than on Earth (2,7). Here, using physical modeling, we drastically lower these estimates. We predict that sand transport can be sustained under winds that are weaker than the strongest possible winds occurring on these planetary bodies. The main reason is entrainment of sand from the surface through impacts of transported particles, which has already been described as the reason for low thresholds on Mars (8). This mechanism requires that sand transport is initiated by processes different from wind erosion, for which we describe several likely candidates. Our study indicates that aeolian sand transport on planetary bodies with very thin atmospheres is much more likely to occur than previously thought and supports the hypothesis that the observed surface features on Triton, Pluto, and 67P formed due to aeolian sand transport. This finding suggests that Pluto's thick haze layer might be at least partially a result of frequent dust aerosol emissions due to aeolian sand transport.