Intraspecific latitudinal clines in the body size of terrestrial vertebrates, where members of the same species are larger at higher latitudes, are widely interpreted as evidence for natural selection and adaptation to local climate. These clines are predicted to shift in response to climate change. We used museum specimens to measure changes in the body size of eight passerine bird species from south-eastern Australia over approximately the last 100 years. Four species showed significant decreases in body size (1.8-3.6% of wing length) and a shift in latitudinal cline over that period, and a meta-analysis demonstrated a consistent trend across all eight species. Southern high-latitude populations now display the body sizes typical of more northern populations pre-1950, equivalent to a 7 degrees shift in latitude. Using ptilochronology, we found no evidence that these morphological changes were a plastic response to changes in nutrition, a likely non-genetic mechanism for the pattern observed. Our results demonstrate a generalized response by eight avian species to some major environmental change over the last 100 years or so, probably global warming.