Immunogenetic variation in natural vertebrate populations is expected to respond to spatial and temporal fluctuations in pathogen assemblages. While spatial heterogeneity in pathogen-driven selection enhances local immunogenetic adaptations and population divergence, different immune genes may yield contrasting responses to the environment. Here, we investigated population differentiation at the key pathogen recognition genes of the innate and adaptive immune system in a colonial bird species, the black-headed gull Chroicocephalus ridibundus. We assessed genetic variation at three toll-like receptor (TLR) genes (innate immunity) and the major histocompatibility complex (MHC) class I and II genes (adaptive immunity) in gulls from seven colonies scattered across Poland. As expected, we found much greater polymorphism at the MHC than TLRs. Population differentiation at the MHC class II, but not MHC-I, was significantly stronger than at neutral microsatellite loci, suggesting local adaptation. This could reflect spatial variation in the composition of extracellular parasite communities (e.g., helminths), possibly driven by sharp differences in habitat structure between colonies. Despite contrasting patterns of population differentiation, both MHC classes showed similar regimes of diversifying selection. Some significant population differentiation was also observed at TLRs, suggesting that innate immune receptors may respond to fine-scale spatial variation in pathogen pressure, although this pattern could have been enhanced by drift. Our results suggested that local adaptation at the pathogen recognition immune genes can be maintained at relatively small or moderate spatial scales in species with high dispersal potential and they highlighted the complexity of immunogenetic responses of animals to heterogeneous environments.