Within-species variation in social structure has attracted interest recently because of the potential to explore phenotypic plasticity and, specifically, how demographic and ecological variation influence social structure. Populations of bottlenose dolphins (Tursiops spp.) vary in male alliance formation, from no alliances to simple pairs to, in Shark Bay, Western Australia, the most complex nested alliances known outside of humans. Examination of ecological contributions to this variation is complicated by differences among populations in other potentially explanatory traits, such as phylogenetic distance, as well as female reproductive schedules, sexual size dimorphism, and body size. Here, we report our discovery of systematic spatial variation in alliance structure, seasonal movements and access to mates within a single continuous social network in the Shark Bay population. Participation in male trios (versus pairs), the sizes of seasonal range shifts and consortship rates all decrease from north to south along the 50 km length of the study area. The southern habitat, characterised by shallow banks and channels, may be marginal relative to the open northern habitat. The discovery of variation in alliance behaviour along a spatial axis within a single population is unprecedented and demonstrates that alliance complexity has an ecological component.