Aspects of birdsong complexity, such as the number of distinct notes in a song, commonly increase along latitudinal gradients, a pattern for which at least 10 explanations have been suggested. In two Himalayan warblers, songs are more complex in the northwest than in the southeast. In Grey‐hooded Warbler Phylloscopus xanthoschistos, high complexity results from increased note diversity within song types, sung across a higher bandwidth. In Blyth's Leaf Warbler Phylloscopus reguloides, high complexity is a consequence of increased variation between song types. The hypothesis with strongest support is that songs evolved to be more complex in species‐poor, demonstrably less noisy environments. We consider geographical variation to be an outcome of sexual selection favouring complexity across environments, where detection of the signal varies. Sexual selection favouring complexity may be resolved in different ways, because complexity has multiple features (repertoire size, song switching, etc.). We argue this has led to the great diversity in song that we have documented among five Phylloscopus species.