When Voyager 2 photographed 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 photographed surface features that have been tentatively interpreted as possible wind streaks when it passed Pluto in 2015 (3). Moreover, Rosetta photographed what look like aeolian ripples and dunes on the comet 67P/Churyumov-Gerasimenko (67P/C-G) 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, using empirical models, it has been estimated that average 1m winds of more than 500km/h are required to transport sand on Triton and Pluto (6), where winds are likely weaker than on Earth (7). Here, using state-of-the-art physical modeling, we drastically lower these estimates. We predict that sand transport can be sustained under average 1m winds as low as 75km/h on Triton and Pluto. We further predict that sand transport on 67P/C-G is possible when considering recent wind shear estimates for the comet surface. Our study indicates that aeolian sand transport on planetary bodies with very thin atmospheres is much more likely to occur than previously thought and strongly supports the hypothesis that the observed surface features on Triton, Pluto, and 67P/C-G 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.