Animals achieve robust locomotion by offloading regulation from the brain to physical couplings within the body. In contrast, locomotion in artificial systems often depends on centralized processors. We introduce a rapid and autonomous locomotion strategy with synchronized gaits emerging through physical interactions between self-oscillating limbs and the environment, without control signals. Each limb is a single soft tube that only requires constant flow of air to perform cyclic stepping motions at frequencies reaching 300 hertz. By combining several of these self-oscillating limbs, their physical synchronization enables locomotion speeds that are orders of magnitude faster than comparable state-of-the-art. Through body-environment dynamics, these seemingly simple devices exhibit autonomy, including obstacle avoidance, amphibious gait transitions, and phototaxis.