Music maintains a characteristic balance between repetition and novelty. Here, we report a similar balance in singing performances of free-living Australian pied butcherbirds. Their songs include many phrase types. The more phrase types in a bird’s repertoire, the more diverse the singing performance can be. However, without sufficient temporal organization, avian listeners may find diverse singing performances difficult to perceive and memorize. We tested for a correlation between the complexity of song repertoire and the temporal regularity of singing performance. We found that different phrase types often share motifs (notes or stereotyped groups of notes). These shared motifs reappeared in strikingly regular temporal intervals across different phrase types, over hundreds of phrases produced without interruption by each bird. We developed a statistical estimate to quantify the degree to which phrase transition structure is optimized for maximizing the regularity of shared motifs. We found that transition probabilities between phrase types tend to maximize regularity in the repetition of shared motifs, but only in birds of high repertoire complexity. Conversely, in birds of low repertoire complexity, shared motifs were produced with less regularity. The strong correlation between repertoire complexity and motif regularity suggests that birds possess a mechanism that regulates the temporal placement of shared motifs in a manner that takes repertoire complexity into account. We discuss alternative musical, mechanistic and ecological explanations to this effect.