Increasing ocean temperatures change growth and mortality of fishes. Changes in growth and mortality are likely to affect fish population size distributions, yet although temperature effects on individual body size are well studied, we have limited knowledge of the impacts to population size distributions. For example, while it is predicted that temperature should lead to declining maximum sizes in fish, an empirical study of 335 fish species from Australia showed that population mean sizes can either decrease or increase with warming. We use size-based population models to explore how temperature impacts on growth (k) and mortality (M) change fish population size structure and their mean and maximum sizes. We show that large variation (up to 40% difference) in mean size occurred under observed M/k ratios and that even when asymptotic size is declining, mean size can still increase by up to 25%. We explore conditions under which mean and maximum sizes change in different directions and show implications of warming driven size structure changes on size-based population model predictions. Changes to population size distributions can have implications for size-based fisheries assessment, stock productivity, and fisheries management. Size structure also plays an important ecological role, governing species interactions and population resilience.