Aim: Allen's rule posits that the appendages of endothermic organisms will be larger in warmer climates to allow for dumping of heat loads. Given a link between appendage size and climate, we tested the prediction that climate change has driven the evolution of larger bills in birds, resulting in measurable changes over the recent past. Location: Australia. Methods: We explored geographical and temporal variation in bill surface area of five Australian parrot species to determine whether individuals from warmer climates have larger bills, and whether there have been increases in bill surface area over time, consistent with climatic warming. Measurements were obtained from museum specimens dating from 1871 to 2008. These data were then related to geographical location, collection date and locality-specific climate data, in order to construct and compare models of spatio-temporal and climate-related variation in bill morphology. Results: There have been increases in bill surface area in mulga parrots (Psephotus varius), gang-gang cockatoos (Callocephalon fimbriatum), red-rumped parrots (Psephotus haematonotus) and male crimson rosellas (Platycercus elegans), equating to a c. 4-10% increase in bill surface area since 1871. Average maximum summer temperature in the 5 years prior to specimen collection also positively predicted bill surface area in mulga parrots, red-rumped parrots and crimson rosellas, consistent with Allen's rule. With the exception of red-rumped parrots, however, models with geographical location and year of collection were still better predictors of bill surface area than local climate at the date of collection. Main conclusions: Our analysis provides evidence that four species of parrot have exhibited adaptive change in bills over the past century potentially mitigating the thermal stress caused by climatic warming. Although consistent with the predicted effects of climate change, the temporal patterns we observe may have additional causes, however, such as changes in primary productivity, habitat or food availability.