Movement strategies of animals have been well studied as a function of ecological drivers (e.g., forage selection and avoiding predation) rather than physiological requirements (e.g., thermoregulation). Thermal stress is a major concern for large mammals, especially for savanna elephants (Loxodonta africana), which have amongst the greatest challenge for heat dissipation in hot and arid environments. Therefore, elephants must make decisions about where and how fast to move to reduce thermal stress. We tracked 14 herds of elephant in Kruger National Park (KNP), South Africa, for 2 years, using GPS collars with inbuilt temperature sensors to examine the influence of temperature on movement strategies, particularly when accessing water. We first confirmed that collar-mounted temperature loggers captured hourly variation in relative ambient temperatures across the landscape, and, thus, could be used to predict elephant movement strategies at fine spatio-temporal scales. We found that elephants moved slower in more densely wooded areas, but, unexpectedly, moved faster at higher temperatures, especially in the wet season compared to the dry season. Notably, this speed of movement was highest when elephants were approaching and leaving water sources. Visits to water showed a periodic shuttling pattern, with a peak return rate of 10–30 h, wherein elephants were closest to water during the hotter times of the day, and spent longer at water sources in the dry season compared to the wet season. When elephants left water, they showed low fidelity to the same water source, and traveled farther in the dry season than in the wet season. In KNP, where water is easily accessible, and the risk of poaching is low, we found that elephants use short, high-speed bursts of movement to get to water at hotter times of day. This strategy not only provides the benefit of predation risk avoidance, but also allows them to use water to thermoregulate. We demonstrate that ambient temperature is an important predictor of movement and water use across the landscape, with elephants responding facultatively to a “landscape of thermal stress.”