Quadrupeds achieve rapid and highly adaptive locomotion owing to the coordination between their legs and other body parts such as their trunk, head, and tail, i.e. body-limb coordination. Therefore, a better understanding of the mechanism underlying body-limb coordination could provide informative insights into the improvement of legged robot mobility. Sprawling locomotion is a walking gait with lateral bending exhibited in primitive legged vertebrates such as salamanders and newts. Because primitive animals are anticipated to possess the essence of quadruped motor control, their locomotion helps better understand body-limb coordination mechanisms. Previous studies modeled neural networks in salamanders and employed it to control robots and investigate and emulate sprawling locomotion. However, these models predefined the relationship between the legs and the trunk, such that how body-limb coordination is attained is largely unknown. In this article, we demonstrate that sensory feedback facilitates body-limb coordination in sprawling locomotion and improves mobility through mathematical modeling and robot simulations. Our proposed model has cross-coupled sensory feedback, that is, bidirectional feedback from body to limb and limb to body, which leads to an appropriate relationship between the legs and the trunk without any predefined relationship. Resulting gaits are similar to the sprawling locomotion of salamanders and achieve high speed and energy efficiency that are at the same level as those of a neural network model, such as conventional models, optimizing the relationship between the legs and the trunk. Furthermore, sensory feedback contributes to the adaptability toward leg failure, and the bidirectionality of feedback facilitates parameter tuning for stable locomotion. These results suggest that cross-coupled sensory feedback facilitates sprawling locomotion and potentially plays an important role in the body-limb coordination mechanism.