<p>Studying animal multilevel societies is important in evolutionary biology as we seek to understand the evolution of complex social systems. Key to this goal is understanding variation in social structure. We studied eight multimale/multifemale core units (MMUs) of a Rwenzori Angolan colobus (<i>Colobus angolensis ruwenzorii</i>) multilevel society over 13 months at Nabugabo, Uganda, where MMUs are common and all-male units are rare. We used social network analyses to describe patterns of spatial proximity (&lt;&#xa0;1 m) among unit members. We found three different patterns of male–female relationships: (1) one male was closest to females while others remained peripheral to the network (<i>N</i>=3), (2) associations were clustered where each male was close to two to three females (<i>N</i>=2), (3) all males showed similar measures of association with females and associated significantly with each other (<i>N</i>=3). Importantly, each of these social structures showed evidence of close male–male associations. Descriptively pairing these data with co-residency and parallel dispersal data from 5 subsequent years suggests that males with more equitable patterns of proximity to females stay together longer and transfer together more often in the future. We conclude that variation in social network structure between core units reflects different strategies used by males to access the benefits of group-living and defend resources, mates, and offspring. Our study provides evidence of lasting male–male relationships in <i>C. a. ruwenzorii</i>, likening them to some other multilevel societies and further supporting that affiliative relationships among the competing sex are an important element to the structuring of multilevel societies in cercopithecids.</p>