Repeated associations among conspecifics are a common feature of social animal species. Such repeated associations may generate social groups which may differ in their foraging or breeding strategy, and ultimately in their fitness. Colonial species breed in large and dense groups which may have favoured the emergence of social benefits and then induce the evolution of group tenacity over years. However, as colonial species are usually highly philopatric, passive individual re-associations over years makes the study of group tenacity in colonial birds challenging. Here, we studied the dynamics of individual associations over years in the Slender-billed gulls, Chroicocephalus genei, a colonial species with low site tenacity over years. We analysed the resightings of 1038 individuals ringed in southern France for 14 years. We found that individual associations were stable across breeding seasons over relatively short time periods (one to three years long). We also found that individuals were significantly more likely to be encountered with conspecifics with which they had been breeding in the previous year than with conspecifics which had bred at other colonies. Finally, we found significant annual variations in group tenacity, with a fission in individual associations following the complete breeding failure of a colony. Our results suggest that group tenacity may be an important featured of habitat selection and population dynamics in colonial birds and that should not be overlooked even in highly philopatric species.