Many cooperatively breeding species live in groups with complex social structure—large group sizes, low but mixed kin structure, and multiple breeding pairs—that form as a result of immigration of unrelated individuals in addition to offspring delaying or foregoing dispersal. Differences in patterns of dispersal can therefore generate variation in social structure, even within the same species or population. Yet, the mechanisms underlying inter-individual variation in dispersal and intraspecific variation in social structure remain poorly studied. Here, we examine how environmentally-mediated dispersal patterns inferred from genetic data influence variation in social structure in the superb starling (Lamprotornis superbus), a complex cooperative breeder that inhabits a spatiotemporally variable savanna environment. Using genome-wide polymorphic loci and remotely-sensed, fine-scale ecological data, we find evidence of not only frequent and long-distance dispersal in both sexes (low isolation-by-distance and weak genetic structure), but also directional dispersal from small groups occupying low-quality territories to large groups occupying high-quality territories. Moreover, we find stronger genetic structure among groups in low-quality territories, but higher genetic diversity and lower overall relatedness of groups in high-quality territories. Long-distance, directional dispersal can thus lead to smaller and simpler kin-based social groups in low-quality territories, but larger and more complex mixed-kin groups in high-quality territories. Thus, individual-level dispersal decisions from lower to higher quality habitat that maximize fitness can generate intraspecific variation in social structure, even within the same population. Such within-population variation in social structure could have profound implications for the mechanisms underlying the formation of cooperative societies more broadly.