Background: Genomic and pathology analysis has revealed enormous diversity in genes involved in disease, including those encoding host resistance and parasite effectors (also known in plant pathology as avirulence genes). It has been proposed that such variation may persist when an organism exists in a spatially structured metapopulation, following the geographic mosaic of coevolution. Here, we study gene-for-gene relationships governing the outcome of plant-parasite interactions in a spatially structured system and, in particular, investigate the population genetic processes which maintain balanced polymorphism in both species. Results: Following previous theory on the effect of heterogeneous environments on maintenance of polymorphism, we analysed a model with two demes in which the demes have different environments and are coupled by gene flow. Environmental variation is manifested by different coefficients of natural selection, the costs to the host of resistance and to the parasite of virulence, the cost to the host of being diseased and the cost to an avirulent parasite of unsuccessfully attacking a resistant host. We show that migration generates negative direct frequency-dependent selection, a condition for maintenance of stable polymorphism in each deme. Balanced polymorphism occurs preferentially if there is heterogeneity for costs of resistance and virulence alleles among populations and to a lesser extent if there is variation in the cost to the host of being diseased. We show that the four fitness costs control the natural frequency of oscillation of host resistance and parasite avirulence alleles. If demes have different costs, their frequencies of oscillation differ and when coupled by gene flow, there is amplitude death of the oscillations in each deme. Numerical simulations show that for a multiple deme island model, costs of resistance and virulence need not to be present in each deme for stable polymorphism to occur. Conclusions: Our theoretical results confirm the importance of empirical studies for measuring the environmental heterogeneity for genetic costs of resistance and virulence alleles. We suggest that such studies should be developed to investigate the generality of this mechanism for the long-term maintenance of genetic diversity at host and parasite genes.