Ectotherms generally shrink under experimental warming, but whether this pattern extends to wild populations is uncertain. We analysed ten million visual survey records, spanning the Australian continent and multiple decades and comprising the most common coastal reef fishes (335 species). We found that temperature indeed drives spatial and temporal changes in fish body size, but not consistently in the negative fashion expected. Around 55% of species were smaller in warmer waters (especially among small-bodied species), while 45% were bigger. The direction of a species' response to temperature through space was generally consistent with its response to temperature increase through time at any given location, suggesting that spatial trends could help forecast fish responses to long-term warming. However, temporal changes were about ten times faster than spatial trends (~4% versus ~40% body size change per 1 °C change through space and time, respectively). The rapid and variable responses of fish size to warming may herald unexpected impacts on ecosystem restructuring, with potentially greater consequences than if all species were shrinking.