The black rat (Rattus rattus) is the main reservoir of plague (Yersinia pestis infection) in Madagascar's rural zones. Black rats are highly resistant to plague within the plague focus (central highland), whereas they are susceptible where the disease is absent (low altitude zone). To better understand plague wildlife circulation and host evolution in response to a highly virulent pathogen, we attempted to determine genetic markers associated with plague resistance in this species. To this purpose, we combined a population genomics approach and an association study, both performed on 249 AFLP markers, in Malagasy R. rattus. Simulated distributions of genetic differentiation were compared to observed data in four independent pairs, each consisting of one population from the plague focus and one from the plague-free zone. We found 22 loci (9% of 249) with higher differentiation in at least two independent population pairs or with combining p-values over the four pairs significant. Among the 22 outlier loci, 16 presented significant association with plague zone (plague focus vs. plague-free zone). Population genetic structure inferred from outlier loci was structured by plague zone, whereas the neutral loci dataset revealed structure by geography (eastern vs. western populations). A phenotype association study revealed that two of the 22 loci were significantly associated with differentiation between dying and surviving rats following experimental plague challenge. The 22 outlier loci identified in this study may undergo plague selective pressure either directly or more probably indirectly due to hitchhiking with selected loci.