Plants and herbivorous insects can each be dramatically affected by temperature. Climate warming may impact plant invasion success directly but also indirectly through changes in their natural enemies. To date, however, there are no tests of how climate warming shifts the interactions among invasive plants and their natural enemies to affect invasion success. Field surveys covering the full latitudinal range of invasive Alternanthera philoxeroides in China showed that a beetle introduced for biocontrol was rare or absent at higher latitudes. In contrast, plant cover and mass increased with latitude. In a 2-year field experiment near the northern limit of beetle distribution, we found the beetle sustained populations across years under elevated temperature, dramatically decreasing A. philoxeroides growth, but it failed to overwinter in ambient temperature. Together, these results suggest that warming will allow the natural enemy to expand its range, potentially benefiting biocontrol in regions that are currently too cold for the natural enemy. However, the invader may also expand its range further north in response to warming. In such cases where plants tolerate cold better than their natural enemies, the geographical gap between plant and herbivorous insect ranges may not disappear but will shift to higher latitudes, leading to a new zone of enemy release. Therefore, warming will not only affect plant invasions directly but also drive either enemy release or increase that will result in contrasting effects on invasive plants. The findings are also critical for future management of invasive species under climate change.