Symbiosis between legumes and nitrogen–fixing bacteria is thought to bring mutual benefit to each participant. However, it is not known how rhizobia benefit from nodulating legume hosts because they fix nitrogen only after becoming bacteroids, which are terminally differentiated cells that cannot reproduce. Because undifferentiated rhizobia in and around the nodule can reproduce, evolution of symbiotic nitrogen fixation may depend upon kin selection. In some hosts, these kin may persist in the nodule as viable, undifferentiated bacteria. In other hosts, no viable rhizobia survive to reproduce after nodule senescence. Bacteroids in these hosts may benefit their free–living kin by enhancing production of plant root exudates. However, unrelated non–mutualists may also benefit from increased plant exudates. Rhizopines, compounds produced by bacteroids in nodules and catabolized only by related free–living rhizobia, may provide a mechanism by which bacteroids can preferentially benefit kin. Despite this apparent advantage, rhizopine genotypes are relatively rare. We constructed a mathematical model to examine how mixing within rhizobium populations influences the evolution of rhizopine genotypes. Our model predicts that the success of rhizopine genotypes is strongly dependent upon the spatial genetic structure of the bacterial population; rhizopine is more likely to dominate well–mixed populations. Further, for a given level of mixing, we find that rhizopine evolves under a positive frequency–dependent process in which stochastic accumulation of rhizopine alleles is necessary for rhizopine establishment. This process leads to increased spatial structure in rhizobium populations, and suggests that rhizopine may expand the conditions under which nitrogen fixation can evolve via kin selection.