Cerebral lateralization refers to the division of information processing in either hemisphere of the brain and is a ubiquitous trait among vertebrates and invertebrates. Given its widespread occurrence, it is likely that cerebral lateralization confers a fitness advantage. It has been hypothesized that this advantage takes the form of enhanced cognitive function, potentially via a dual processing mechanism whereby each hemisphere can be used to process specific types of information without contralateral interference. Here, we examined the influence of lateralization on problem solving by Australian parrots. The first task, a pebble-seed discrimination test, was designed for small parrot species that feed predominately on small seeds, which do not require any significant manipulation with the foot prior to ingestion. The second task, a string-pull problem, was designed for larger bodied species that regularly use their feet to manipulate food objects. In both cases, strongly lateralized individuals (those showing significant foot and eye biases) outperformed less strongly lateralized individuals, and this relationship was substantially stronger in the more demanding task. These results suggest that cerebral lateralization is a ubiquitous trait among Australian parrots and conveys a significant foraging advantage. Our results provide strong support for the enhanced cognitive function hypothesis.