To escape danger or catch prey, running vertebrates rely on dynamic gaits with minimal ground contact. By contrast, most insects use a tripod gait that maintains at least three legs on the ground at any given time. One prevailing hypothesis for this difference in fast locomotor strategies is that tripod locomotion allows insects to rapidly navigate three-dimensional terrain. To test this, we computationally discovered fast locomotor gaits for a model based on Drosophila melanogaster. Indeed, the tripod gait emerges to the exclusion of many other possible gaits when optimizing fast upward climbing with leg adhesion. By contrast, novel two-legged bipod gaits are fastest on flat terrain without adhesion in the model and in a hexapod robot. Intriguingly, when adhesive leg structures in real Drosophila are covered, animals exhibit atypical bipod-like leg coordination. We propose that the requirement to climb vertical terrain may drive the prevalence of the tripod gait over faster alternative gaits with minimal ground contact.