Song repertoire size is often cited as a classic example of a secondary sexual trait in birds. Models of sexual selection and empirical tests of their predictions have often related secondary sexual traits to longevity. However, the relationship between repertoire size and longevity is unclear. Using capture-mark-recapture studies in two populations of the brownish-flanked bush warbler Cettia fortipes, we found that males with a repertoire size of three maintained territory tenure for a longer duration than did males with a repertoire size of two. These results provide evidence that even a minimal difference in repertoire size can serve as a potential signal of territory tenure capability.