In species with mate choice, the choosy sex selects its mate based on traits that are thought to indicate the mate's quality. In several bird species, females prefer males that sing more complex songs but it is unclear which aspect of male quality is signalled by this trait. Here we tested the hypothesis that a male's song complexity conveys information about his learning capacity. We recorded the songs of 27 male zebra finches, Taeniopygia guttata, and quantified their complexity by measuring average song phrase duration, the total number of elements and the number of unique elements per song phrase. We then presented each male with a novel foraging task and recorded the number of trials he required to solve the task. We found a positive correlation between song complexity and learning proficiency: males with more song phrase elements required fewer learning trials to solve the novel foraging task. This result suggests that a male's song complexity signals his learning ability, which may have contributed to the selective pressures driving females to choose males with more complex songs. (C) 2008 The Association for the Study of Animal Behaviour. Published by Elsevier Ltd. All rights reserved.