Numerous reports have documented the occurrence of same-sex sociosexual behaviour (SSB) across animal species. However, the distribution of the behaviour within a species is needed to test the theories describing its evolution and maintenance, in particular whether the behaviour is heritable and can therefore evolve by natural selection. Here, we collected detailed observations across three years of social and mounting behaviour of 236 male semi-wild rhesus macaques, which we combined with a pedigree dating back to 1938, to show that SSB was both repeatable (19.35%) and heritable (6.4%). Demographic factors (age and group structure) explained SSB variation only marginally. Furthermore, we found a positive genetic correlation between same-sex mounter and mountee activities, indicating a common basis to different forms of SSB. Finally, we found no evidence of fitness costs to SSB, but show instead that the behaviour mediated coalitionary partnerships that have been linked with improved reproductive success. Together, our results demonstrate that SSB is frequent in rhesus macaques, can evolve, and is not costly, indicating that SSB may be a common feature of primate reproductive ecology.