The largest animals in the oceans eat prey that are orders of magnitude smaller than themselves, implying strong selection for cost-effective foraging to meet their energy demands. Whale sharks (Rhincodon typus) may be especially challenged by warm seas that elevate their metabolism and contain sparse prey resources. Using a combination of biologging and satellite tagging, we show that whale sharks use four strategies to save energy and improve foraging efficiency: 1) fixed, low power swimming, 2) constant low speed swimming, 3) gliding and 4) asymmetrical diving. These strategies increase foraging efficiency by 22 – 32% relative to swimming horizontally and resolve the energy-budget paradox of whale sharks. However, sharks in the open ocean must access food resources that reside in relatively cold waters (up to 20oC cooler than the surface) at depths of 250-500 m during the daytime, where long, slow gliding descents, continuous ram ventilation of the gills and filter-feeding could rapidly cool the circulating blood and body tissues. We suggest that whale sharks may overcome this problem through their large size and a specialized body plan that isolates highly vascularized red muscle on the dorsal surface, allowing heat to be retained near the centre of the body within a massive core of white muscle. This could allow a warm-adapted species to maintain enhanced function of organs and sensory systems while exploiting food resources in deep, cool water.