Multi-legged animals such as centipedes move effectively in diverse terrain; limb-body coordination and flexible body parts allow them to morphologically adapt to the environment. To understand the importance of body morphology and complex, dynamic interactions between an organism and its environment, we built a low-cost multi-legged hybrid (containing soft and hard components) 70 cm robot which has 8 segments, each with two limbs driven out of phase. The back elements and limb pairs are driven by servo motors. Building on theoretical results from geometric mechanics, we systematically tested gait patterns with different leg contacts and body undulations on laboratory environments including flat and uneven rigid ground. On flat ground, the robot with rigid components moved in the same way as the theoretically predicted gaits. As the roughness of the surface increased, the robot’s performance suffered (and theoretical predictions became unavailable) due to deleterious interactions like jamming of limbs. However, addition of directional compliance into the robot’s legs and soft elements at two body segments improved the open-loop locomotion performance (often to levels of that on flat ground) by either reducing the effects of environmental disturbances or increasing stability. Remarkably, without sensing and active feedback, the robot can traverse complex terrestrial ground like grass, leaf litter and stair-steps, pointing yet again to the importance of mechanics in control of locomotion.