Male song sparrows sing repertoires of 4–13 distinct song types and have proved a valuable model for testing hypotheses concerning the function and evolution of song complexity. Captive female song sparrows solicit more copulations in response to playback of larger repertoires, yet it remains unclear whether male repertoire size influences female mate choice in natural situations. We used long-term data from free-living song sparrows inhabiting Mandarte Island, British Columbia, Canada, to investigate whether male song repertoire size predicted three components of reproductive performance during the first year: territory acquisition, mating success and laying date. Across males whose song was recorded, males with larger repertoires were not more likely to acquire a territory, to acquire a larger territory or to settle sooner. However, after we controlled for territory size and between-year variation in the population sex ratio, first-year males with larger repertoires were more likely to mate. This was because they were more likely to pair with newly settled females, not because they were more likely to acquire territories where older females were already resident. After we controlled for territory size and between-year variation in breeding date, newly settled females laid earlier when mated with males with larger repertoires. Together with the results of previous mate choice experiments, these patterns are consistent with the hypothesis that male song repertoire size is a sexually selected trait that influences female mate choice in song sparrows.