In contrast to most mammalian social systems, a few primate species, including early humans, live in multilevel societies (MLS) in which multiple family units co-exist to form a breeding band of several hundred individuals and an associated all-male band (AMB). Although the primate MLS has importance for understanding the origin of human sociality, previous research has focused mainly on African papionins, revealing that the papionin MLS evolved from an internal fissioning process from a large multi-male/multi-female group. Based on a combination of social network analysis, satellite telemetry, and genetic investigation, we estimated the dynamic of interactions between bachelor males to restructure their affiliation patterns, and cooperative and tolerance behaviors, to form and maintain a large AMB in the golden snub-nosed monkey (Rhinopithecus roxellana). We found that bachelor males form stronger alliances when they approach breeding females. Using a novel HPMT mathematical model, we show that kinship was the most important factor facilitating alliance formation among AMB males, followed by age and dominance rank. We suggest that an ‘arms race’ between breeding males’ collective defense against usurpation attempts by bachelor males, and bachelor males’ aggregative offense to obtain reproductive opportunities, has selected for larger group size on both sides. This provides further support for the R. roxellana MLS having evolved from a fusion of a network of small, isolated family groups in an ancestral Asian colobine, as well as increasing understanding of human social evolution, because male-male affiliations are trademarks of small- and large-scale human societies.