On one side, field studies carried over the past 50 years provided convincing and abundant evidence of neighbour vocal recognition in male songbirds. On the other side, the high degree of breeding site fidelity of many songbirds often results in the existence of stable inter-annual neighbour communities. This may select for an ability to discriminate between neighbours and strangers in the long-term. We addressed this question by focusing on territorial relationships and vocalizations stability over two breeding seasons in a migratory songbird, the black redstart, Phoenicurus ochruros - a species with a small vocal repertoire (2-4 song types). The song type repertoire of adult males is stable from one breeding season to the next. Males share most of their songs with neighbours (81%) but there is only limited sharing with strangers (15%). Individual differences exist in the rendition of the same song type by two neighbouring birds and these differences also persist from one year to the next. Males responded less aggressively to the playback of a neighbour song (often shared by the tested bird) than to a stranger unfamiliar song. A few birds were tested with the same stimuli when returning from migration and they tended to react less aggressively to their last year neighbour’s song. We discuss the implications of our results for song learning strategies and recognition abilities in a long-term memory framework.