Mycoplasmas exhibit a novel, substrate-dependent gliding motility that is driven by approximately 400 "leg" proteins. The legs interact with the substrate and transmit the forces generated by an assembly of ATPase motors. The velocity of the cell increases linearly by nearly 10-fold over a narrow temperature range of 10-40 degrees C. This corresponds to an Arrhenius factor that decreases from approximately 45 k(B)T at 10 degrees C to approximately 10 k(B)T at 40 degrees C. On the other hand, load-velocity curves at different temperatures extrapolate to nearly the same stall force, suggesting a temperature-insensitive force-generation mechanism near stall. In this article, we propose a leg-substrate interaction mechanism that explains the intriguing temperature sensitivity of this motility. The large Arrhenius factor at low temperature comes about from the addition of many smaller energy barriers arising from many substrate-binding sites at the distal end of the leg protein. The Arrhenius dependence attenuates at high temperature due to two factors: 1), the reduced effective multiplicity of energy barriers intrinsic to the multiple-site binding mechanism; and 2), the temperature-sensitive weakly facilitated leg release that curtails the power stroke. The model suggests an explanation for the similar steep, sub-Arrhenius temperature-velocity curves observed in many molecular motors, such as kinesin and myosin, wherein the temperature behavior is dominated not by the catalytic biochemistry, but by the motor-substrate interaction.