To navigate different environments, an animal must be able to adapt its locomotory gait to its physical surroundings. The nematode Caenorhabditis elegans, between swimming in water and crawling on surfaces, adapts its locomotory gait to surroundings that impose approximately 10,000-fold differences in mechanical resistance. Here we investigate this feat by studying the undulatory movements of C. elegans in Newtonian fluids spanning nearly five orders of magnitude in viscosity. In these fluids, the worm undulatory gait varies continuously with changes in external load: As load increases, both wavelength and frequency of undulation decrease. We also quantify the internal viscoelastic properties of the worm's body and their role in locomotory dynamics. We incorporate muscle activity, internal load, and external load into a biomechanical model of locomotion and show that (i) muscle power is nearly constant across changes in locomotory gait, and (ii) the onset of gait adaptation occurs as external load becomes comparable to internal load. During the swimming gait, which is evoked by small external loads, muscle power is primarily devoted to bending the worm's elastic body. During the crawling gait, evoked by large external loads, comparable muscle power is used to drive the external load and the elastic body. Our results suggest that C. elegans locomotory gait continuously adapts to external mechanical load in order to maintain propulsive thrust.