The transition to air-breathing by formerly aquatic species has occurred repeatedly and independently in fish, crabs and other animal phyla, but the proximate drivers of this key innovation remain a long-standing puzzle in evolutionary biology. Most studies attribute the onset of air-breathing to the repeated occurrence of aquatic hypoxia; however, this hypothesis leaves the current geographical distribution of the 300 genera of air-breathing crabs unexplained. Here, we show that their occurrence is mainly related to high environmental temperatures in the tropics. We also demonstrate in an amphibious crab that the reduced cost of oxygen supply in air extends aerobic performance to higher temperatures and thus widens the animal's thermal niche. These findings suggest that high water temperature as a driver consistently explains the numerous times air-breathing has evolved. The data also indicate a central role for oxygen- and capacity-limited thermal tolerance not only in shaping sensitivity to current climate change but also in underpinning the climate-dependent evolution of animals, in this case the evolution of air-breathing.