Bird songs are among the most complex sounds produced by animals. Song complexity is thought to have evolved largely through intersexual selection. However, this complexity may hinder vocal recognition, which plays an important role in a variety of social contexts, including neighbour recognition during territory defence. We investigated the influence of song complexity on neighbour recognition in a territorial songbird with a highly complex song, the skylark (Alauda arvensis). This bird is a territorial species of open landscape in which pairs settle in stable territories during the breeding season. Due to the heterogeneity of the habitat, territories are gathered in patches spaced by few kilometres. We first carried out a detailed analysis of songs to describe song syntax (the organisation of sound units in sequences within songs) and to measure song complexity. We showed that skylark songs are among the most complex acoustic signals compared to other songbird species, and that geographical variation exists at the syntax level: in a given patch, males (neighbours) share several sequences of syllables in their songs, whereas males settled in different patches (strangers) have no sequences in common. We then tested neighbour recognition using natural and artificially modified songs. Results showed that the syntax of sequences shared by neighbours encodes the neighbourhood identity in the complex song of the species and is used by birds to discriminate neighbours from strangers. The ordering of syllables within songs is thus behaviourally salient and carries a particular meaning for the birds.