Animals achieve robust locomotion by offloading regulation from the brain to physical couplings within the body. Contrarily, locomotion in artificial systems often depends on centralized processors. Here, 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 tethered and untethered locomotion speeds that are orders of magnitude faster than comparable state-of-the-art. We demonstrate that these seemingly simple devices exhibit autonomy, including obstacle avoidance and phototaxis, opening up avenues for robust and functional robots at all scales.