Ancient population expansions and dispersals often leave enduring signatures in the cultural traditions of their descendants, as well as in their genes and languages. The international folktale record has long been regarded as a rich context in which to explore these legacies. To date, investigations in this area have been complicated by a lack of historical data and the impact of more recent waves of diffusion. In this study, we introduce new methods for tackling these problems by applying comparative phylogenetic methods and autologistic modelling to analyse the relationships between folktales, population histories and geographical distances in Indo-European-speaking societies. We find strong correlations between the distributions of a number of folktales and phylogenetic, but not spatial, associations among populations that are consistent with vertical processes of cultural inheritance. Moreover, we show that these oral traditions probably originated long before the emergence of the literary record, and find evidence that one tale (‘The Smith and the Devil’) can be traced back to the Bronze Age. On a broader level, the kinds of stories told in ancestral societies can provide important insights into their culture, furnishing new perspectives on linguistic, genetic and archaeological reconstructions of human prehistory.