Legged locomotion is the most common behavior of terrestrial animals and it is assumed to have become highly optimized during evolution. Quadrupeds, for instance, use distinct gaits that are optimal with regard to metabolic cost and have characteristic kinematic features and patterns of inter-leg coordination. In insects, the situation is not as clear. In general, insects are able to alter inter-leg coordination systematically with locomotion speed, producing a continuum of movement patterns. This notion, however, is based on the study of several insect species, which differ greatly in size and mass. Each of these species tends to walk at a rather narrow range of speeds. We have addressed these issues by examining four strains of Drosophila, which are similar in size and mass, but tend to walk at different speed ranges. Our data suggest that Drosophila controls its walking speed almost exclusively via step frequency. At high walking speeds, we invariably found tripod coordination patterns, the quality of which increased with speed as indicated by a simple measure of tripod coordination strength (TCS). At low speeds, we also observed tetrapod coordination and wave gait-like walking patterns. These findings not only suggest a systematic speed dependence of inter-leg movement patterns but also imply that inter-leg coordination is flexible. This was further supported by amputation experiments in which we examined walking behavior in animals after the removal of a hindleg. These animals show immediate adaptations in body posture, leg kinematics and inter-leg coordination, thereby maintaining their ability to walk.