Sea stars use hundreds of tube feet on their oral surface to crawl, climb, and navigate complex environments, all without the coordination of a central brain. While the morphology of tube feet and their role as muscular hydrostats are well described, the dynamics underlying their locomotion remain poorly understood. To investigate these dynamics, we employed an optical imaging method based on frustrated total internal reflection to visualize and quantify tube foot adhesion in real time across individuals of Asterias rubens spanning a wide size range. Our results reveal an inverse relationship between crawling speed and the duration of tube foot contact with the substrate. This suggests that sea stars regulate locomotion by modulating foot-substrate interaction time in response to body load. To test this, we conducted perturbation experiments using 3D-printed backpacks that increased body mass by 25% and 50%, along with numerical simulations based on a mechanistic model incorporating decentralized feedback control of the tube feet. The added load significantly increased adhesion time, supporting the role of a load-dependent mechanical adaptation. We further investigated inverted locomotion, both experimentally and through simulation, and found that tube feet adjust their contact behavior when the animal is oriented upside down relative to gravity. Together, our findings demonstrate that sea stars adapt their locomotion to changing mechanical demands by modulating tube foot-substrate interactions, revealing a robust, decentralized strategy for navigating diverse and challenging terrains.