Culture, defined as socially transmitted information and behaviors that are shared in groups and persist over time, is increasingly accepted to occur across a wide range of taxa and behavioral domains. While persistent, cultural traits are not necessarily static, and their distribution can change in frequency and type in response to selective pressures, analogous to that of genetic alleles. This has lead to the treatment of culture as an evolutionary process, with cultural evolutionary theory arguing that culture exhibits the three fundamental components of Darwinian evolution: variation, competition, and inheritance. Selection for more efficient behaviors over alternatives is a crucial component of cumulative cultural evolution, yet our understanding of how and when such cultural selection occurs in non-human animals is limited. We performed a cultural diffusion experiment using 18 captive populations of wild-caught great tits (Parus major) to ask whether more efficient foraging traditions are selected for, and whether this process is affected by a fundamental demographic process—population turnover. Our results showed that gradual replacement of individuals with naive immigrants greatly increased the probability that a more efficient behavior invaded a population’s cultural repertoire and out-competed an established inefficient behavior. Fine-scale, automated behavioral tracking revealed that turnover did not increase innovation rates, but instead acted on adoption rates, as immigrants disproportionately sampled novel, efficient behaviors relative to available social information. These results provide strong evidence for cultural selection for efficiency in animals, and highlight the mechanism that links population turnover to this process.