Terrestrial vertebrates worldwide gain critical information about danger by eavesdropping on other species’ alarm calls, providing an excellent context to study information flow among species in animal communities. A fundamental but not fully resolved question is how individuals recognize other species’ calls. Although individuals respond to heterospecific calls that are acoustically similar to their own, alarm calls vary greatly among species and eavesdropping probably also requires learning. Surprisingly, however, there have been no fully controlled studies showing the importance of learning when eavesdropping on alarm calls. We show experimentally that individual wild superb fairy-wrens, Malurus cyaneus, can learn to recognize unfamiliar alarm calls. Individuals were trained by broadcasting novel sounds while simultaneously presenting a gliding predatory bird. Fairy-wrens originally ignored these sounds, but most fled to the sounds after two days’ training. The learned response was not due to increased responsiveness in general, because birds did not flee to novel sounds to which they were not trained. The response was also not due to sensitization following repeated exposure, and was independent of novel call structure. Learning can therefore help explain eavesdropping, despite variation in alarm calls among species, and so can tailor behaviour to the local community of predators and prey. In combination with previous work showing that alarm signals can facilitate novel predator recognition, our results imply rapid spread of anti-predator behaviour within wild populations.