Animals navigate their environment stably without inefficient course corrections despite unavoidable errors. In humans and some robots, this stability is achieved by controlling the placement of the foot on the ground such that recent movement errors are corrected. However, it is unknown how animals with diverse nervous systems and body mechanics use foot placement control: foot trajectories of many-legged animals are thought to be stereotypical velocity-driven patterns, as opposed to error-driven. Here, we posit a unified "feedforward-feedback" control structure for stabilizing foot placement by combining velocity-driven and body state error-driven contributions. We provide empirical support for this unified control structure across flies, mice and humans by mining the variability in the foot placements and body states during natural locomotion. We find that a competing "feedforward-only" control structure with purely velocity-driven foot placement is not supported by the data. This work discovers shared behavioral signatures of error-dependent foot placement control during natural locomotion in flies, mice, and humans. We find that the urgency and centralization of the foot placement control signatures vary with the animal's neuromechanical embodiment; more inherently stable many-legged embodiment is associated with a lower control magnitude and timescale. Further, many-legged embodiment is accompanied by modular direction- and leg-specific signatures, which are centralized across both legs in humans. Taken together, our findings provide insight into stabilizing foot placement control across species, revealing how different neuromechanical embodiments achieve a shared functional goal.