Bird song is the primary animal model system for cultural evolution. Longitudinal studies of bird song across many generations can provide insights into patterns and mechanisms of change in socially transmitted traits. In this study, we conducted a comparative analysis of songs of the House Finch (Haemorhous mexicanus) across an interval of 37 years (in 1975 and in 2012). Recordings from both years were collected in western Long Island, New York, which is thought to be the initial site of introduction of the House Finch around 1940 from the West Coast. Song types experienced a complete turnover during this period, although half of the syllable types were represented in both samples. Song length, frequency bandwidth and several other spectrographic features were the same in both years, and no structural features predicted recurrence of individual syllables. Consistent with the fact that our study population expanded substantially following a cultural founder effect, song and syllable sharing and similarity between individuals were lower in 2012 than in 1975, reflecting an increase in song diversity at the population level. However, in the more recent sample individual songs had fewer syllables, and were sung with less sequence stereotypy across renditions than in the earlier sample. Syllable prevalence in 2012 was associated both with complexity (as gauged by frequency excursion) and increased minimum frequency. Thus, over nearly 4 decades, Eastern House Finch songs remained structurally similar at the whole-song level, diversified between individuals, but became simpler and less consistent within an individual.