We investigate the relationship between cultural complexity and population size in a non-technological cultural domain for which we have suitable quantitative records: folktales. We define three levels of complexity for folk narratives: the number of tale types, the number of narrative motifs, and, finally, the number of traits in variants of the same type, for two well-known tales for which we have data from previous studies. We found a positive relationship between number of tale types and population size, a negative relationship for the number of narrative motifs, and no relationship for the number of traits. The absence of a consistent relationship between population size and complexity in folktales provides a novel perspective on the current debates in cultural evolution. We propose that the link between cultural complexity and demography could be domain dependent: in some domains (e.g. technology) this link is important, whereas in others, such as folktales, complex traditions can be easily maintained in small populations as well as large ones, as they may appeal to universal cognitive biases.