Understanding the correlated evolution of brain size and behavior has interested biologists for decades. Many studies have investigated the relationship between brain size and behavior, but the majority of these, are correlational and therefore do not test whether evolutionary changes in brain size precede behavior, or vice versa. Here we address this gap by using phylogenetic generalized least squares (PGLS) regression to test for associations between brain size and foraging tactics in woodpeckers. We then explore various evolutionary scenarios through discrete trait modeling and reversible jump Markov chain Monte Carlo (rjMCMC) analyses. This last method allowed us to estimate evolutionary timelines by assessing likelihoods of certain evolutionary transitions between states of binary traits. We show that woodpecker species that rely heavily on extractive foraging techniques, specifically those that feed on wood-boring larvae from trees, have a larger brain relative to body size. Moreover, extractive foraging and brain size coevolve, such that the ability to feed on these larvae only arises in species that retained an ancestral large brain. Thus, larger brains ‘evolve first’ and could provide the computational capacity needed to evolve extractive foraging behavior and occupy new ecological niches.