Climate change is rapidly altering the distributions of species and the composition of communities that have evolved over evolutionary time scales. Quantifying changes in species distributions and abundance in response to warming is critical to understanding how these changes modify structure, function and services provided by recipient communities. Changes in size structure of warm- and cool-affiliated species is an important indicator for climate-driven species redistributions over time, and has received relatively little attention. We quantified changes in length and biomass distributions of 25 species of Labridae fishes from 112 sites spanning 2000 km across a warm-cool temperate transition zone in south Western Australia. Length and biomass data were collected in 2005-2006 and 2014-2015 using diver operated stereo-video. In the decade between sampling events, south Western Australia experienced an extreme marine heatwave followed by repeated summers of anomalously warm ocean temperatures. Biomass of tropical and subtropical species increased 10-fold and 3-fold, respectively, between 2006 and 2015, whereas temperate species biomass remained relatively stable. In 2014-2015, the abundance and biomass of tropical species (e.g. Scarus ghobban) increased in the warmest regions and established multiple size classes poleward of their recorded 2005-2006 distributions, suggesting successful overwintering and recruitment where viable populations were not recorded in 2005-2006. Large, slow-growing temperate species such as Achoerodus gouldii and Bodianus frenchii decreased in small and medium size classes in warm regions. Our findings report a substantial change in the size structure and composition of labrid assemblages over a decade of climatic variability.