Some oscine songbird species modify their songs throughout their lives ('adult song plasticity' or 'open-ended learning'), while others crystallize their songs around sexual maturity. It remains unknown whether the strength of sexual selection on song characteristics, such as repertoire size, affects adult song plasticity, or whether adult song plasticity affects song evolution. Here, we compiled data about song plasticity, song characteristics, and mating system and then examined evolutionary interactions between these traits. Across 67 species, we found that lineages with adult song plasticity show directional evolution toward increased syllable and song repertoires, while several other song characteristics evolved faster, but in a non-directional manner. Song plasticity appears to drive bi-directional transitions between monogamous and polygynous social mating systems. Notably, our analysis of correlated evolution suggests that extreme syllable and song repertoire sizes drive the evolution of adult song plasticity or stability, providing novel evidence that sexual selection may indirectly influence open- versus closed-ended learning.