The response of tropical cyclone activity to global warming is widely debated. It is often assumed that warmer sea surface temperatures provide a more favourable environment for the development and intensification of tropical cyclones, but cyclone genesis and intensity are also affected by the vertical thermodynamic properties of the atmosphere. Here we use climate models and observational reconstructions to explore the relationship between changes in sea surface temperature and tropical cyclone 'potential intensity'--a measure that provides an upper bound on cyclone intensity and can also reflect the likelihood of cyclone development. We find that changes in local sea surface temperature are inadequate for characterizing even the sign of changes in potential intensity, but that long-term changes in potential intensity are closely related to the regional structure of warming; regions that warm more than the tropical average are characterized by increased potential intensity, and vice versa. We use this relationship to reconstruct changes in potential intensity over the twentieth century from observational reconstructions of sea surface temperature. We find that, even though tropical Atlantic sea surface temperatures are currently at a historical high, Atlantic potential intensity probably peaked in the 1930s and 1950s, and recent values are near the historical average. Our results indicate that--per unit local sea surface temperature change--the response of tropical cyclone activity to natural climate variations, which tend to involve localized changes in sea surface temperature, may be larger than the response to the more uniform patterns of greenhouse-gas-induced warming.