Culture (behaviour based on socially transmitted information) is present in diverse animal species, yet how it interacts with genetic evolution remains largely unexplored. Here, we review the evidence for gene-culture coevolution in animals, especially birds, cetaceans and primates. We describe how culture can relax or intensify selection under different circumstances, create new selection pressures by changing ecology or behaviour, and favour adaptations, including in other species. Finally, we illustrate how, through culturally mediated migration and assortative mating, culture can shape population genetic structure and diversity. This evidence suggests strongly that animal culture plays an important evolutionary role, and we encourage explicit analyses of gene-culture coevolution in nature.