The increased temperature associated with climate change may have important effects on body size and predator-prey interactions. The consequences of these effects for food web structure are unclear because the relationships between temperature and aspects of food web structure such as predator-prey body-size relationships are unknown. Here, we use the largest reported dataset for marine predator-prey interactions to assess how temperature affects predator-prey body-size relationships among different habitats ranging from the tropics to the poles. We found that prey size selection depends on predator body size, temperature and the interaction between the two. Our results indicate that (i) predator-prey body-size ratios decrease with predator size at below-average temperatures and increase with predator size at above-average temperatures, and (ii) that the effect of temperature on predator-prey body-size structure will be stronger at small and large body sizes and relatively weak at intermediate sizes. This systematic interaction may help to simplify forecasting the potentially complex consequences of warming on interaction strengths and food web stability.