In human societies, cultural norms arise when behaviours are transmitted with high-fidelity social learning through social networks1. However a paucity of experimental studies has meant that there is no comparable understanding of the process by which socially transmitted behaviours may spread and persist in animal populations2,3. Here, we introduce alternative novel foraging techniques into replicated wild sub-populations of great tits (Parus major), and employ automated tracking to map the diffusion, establishment and long-term persistence of seeded behaviours. We further use social network analysis to examine social factors influencing diffusion dynamics. From just two trained birds in each sub-population, information spread rapidly through social network ties to reach an average of 75% of individuals, with 508 knowledgeable individuals performing 58,975 solutions. Sub-populations were heavily biased towards the technique originally introduced, resulting in established local arbitrary traditions that were stable over two generations, despite high population turnover. Finally, we demonstrate a strong effect of social conformity, with individuals disproportionately adopting the most frequent local variant when first learning, but then also continuing to favour social over personal information by matching their technique to the majority variant. Cultural conformity is thought to be a key factor in the evolution of complex culture in humans4-7. In providing the first experimental demonstration of conformity in a wild non-primate, and of cultural norms in foraging techniques in any wild animal, our results suggest a much wider evolutionary occurrence of such apparently complex cultural behaviour.