Species redistributions in response to climate change are reshuffling the composition of ecosystems globally. How these changes are altering ecosystem processes, however, remains poorly understood. Here we examine how the impacts of herbivory change across a gradient of tropicalisation in the Mediterranean Sea, that includes a steep climatic gradient and marked changes in plant nutritional quality and fish herbivore composition from native cool-affiliated species to primarily non-native warm-affiliated species. We quantified individual per-capita feeding rates and behaviour of 755 individuals and we measured herbivore and benthic assemblage composition along the gradient which spanned 30º of longitude and 8º of latitude. We coupled patterns with in situ temperature measurements and plant nutrient concentrations from each location, to assess their relationship to observed patterns in herbivory. We found a transition in ecological impacts by fish herbivory across the Mediterranean from a predominance of seagrass herbivory in the cool west to a dominance of macroalgal herbivory in the tropicalised east. Underlying this shift in ecological impacts were changes in both individual feeding behaviour and assemblage composition. Our findings highlight how herbivory can contribute to the increased vulnerability of seaweed communities and reduced vulnerability of seagrass meadows in warmer, tropicalised ecosystems.