In the self-incompatibility (SI) system, male and female S alleles are tightly linked to prevent self-fertilization of pollen and pistils having the same S alleles. Is such a tight linkage necessary for the initial evolution of SI? We theoretically examined whether male and female S alleles stably co-exist in a population without a tight linkage, assuming gametophytic SI. Consider Sm and Nm alleles for the male locus and Sf and Nf alleles for the female locus. The cross between pollen having Sm alleles and pistils having Sf alleles is incompatible, whereas other crosses are compatible. Pollen having Sm alleles and ovules in the pistils having Sf alleles suffer from survival cost due to resource consumption for recognition. We found that Sm and Sf alleles stably co-exist with moderate linkage due to the cost of having Sf alleles. This is because parents having Sf alleles but a homozygote of Nm alleles cannot avoid self-fertilization and suffering from survival cost, and hence Nm alleles are selected against. Thus, Sm alleles spread because ovules, not pollen, having these alleles spread. We suggest that, if Sm and Sf alleles stably co-exist, mutations enhancing their linkage are selected for, leading to their tight linkage.