Culture evolves, but the existence of cross-culturally general regularities of cultural evolution is debated. As a diverse but universal cultural phenomenon, music provides a novel domain to test for the existence of such regularities. Folk song melodies can be thought of as culturally transmitted sequences of notes that change over time under the influence of cognitive and acoustic/physical constraints. Modeling melodies as evolving sequences constructed from an “alphabet” of 12 scale degrees allows us to quantitatively test for the presence of cross-cultural regularities using a sample of 10,062 melodies from musically divergent Japanese and English (British/American) folk song traditions. Our analysis identifies 328 pairs of highly related melodies, finding that note changes are more likely when they have smaller impacts on a song’s melody. Specifically, (1) notes with stronger rhythmic functions are less likely to change, and (2) note substitutions are most likely between neighboring notes. We also find that note insertions/deletions (“indels”) are more common than note substitutions, unlike genetic evolution where the reverse is true. Our results are consistent across English and Japanese samples despite major differences in their scales and tonal systems. These findings demonstrate that even a creative art form such as music is subject to evolutionary constraints analogous to those governing the evolution of genes, languages, and other domains of culture.