Abstract: Animal groups arise from individuals’ choices about the number, characteristics, and identity of associates. Individuals make these choices to gain benefits from their associations. As the needs of an individual change with its phenotype, so too we expect the nature of its associations to vary. In this paper, we investigate how the social priorities of male plains zebra (Equus burchelli) depend on reproductive state. An adult male is either a bachelor, and lacking mating access, or a stallion defending a harem. Multiple harems and bachelor males aggregate in larger herds. Herds frequently split and merge, affording males opportunities to change associates. Over a 4-year period, we sampled the herd associations in a population of 500–700 zebras. To isolate the effects of reproductive state on male social behavior, we account for potential confounding factors: changes in population size, grouping tendencies, and sampling intensity. We develop a generally applicable permutation procedure, which allows us to test the null hypothesis that social behavior is independent of male status. Averaging over all individuals in the population, we find that a typical bachelor is found in herds containing significantly more adults, bachelors, and stallions than the herds of a typical stallion. Further, bachelors’ bonds with each other are more persistent over time than those among stallions. These results suggest that bachelors form cohesive cliques, in which we may expect cooperative behaviors to develop. Stallion–stallion associations are more diffuse, and less conducive to long-term cooperation.