The evolution of cooperation often depends upon population structure, yet nearly all models of cooperation implicitly assume that this structure remains static. This is a simplifying assumption, because most organisms possess genetic traits that affect their population structure to some degree. These traits, such as a group size preference, affect the relatedness of interacting individuals and hence the opportunity for kin or group selection. We argue that models that do not explicitly consider their evolution cannot provide a satisfactory account of the origin of cooperation, because they cannot explain how the prerequisite population structures arise. Here, we consider the concurrent evolution of genetic traits that affect population structure, with those that affect social behavior. We show that not only does population structure drive social evolution, as in previous models, but that the opportunity for cooperation can in turn drive the creation of population structures that support it. This occurs through the generation of linkage disequilibrium between socio-behavioral and population-structuring traits, such that direct kin selection on social behavior creates indirect selection pressure on population structure. We illustrate our argument with a model of the concurrent evolution of group size preference and social behavior.