In social mammals, dominance status and tenure length are often important determinants of male reproductive success. Nevertheless, alternative strategies, such as extra-pair mating and the active role of females in securing reproductive benefits, can substantially modify patterns of paternity. To date, many studies have had short observation periods and small sample sizes, constraining understanding of how male social status, tenure length, and female mating strategies jointly affect male long-term reproductive success, especially in species with complex social systems. Using longitudinal demographic and genetic data from a free-ranging population of a golden snub-nosed monkey (Rhinopithecus roxellana) multilevel society in the Qinling Mountains, central China, we investigated how leader males' ranks and tenure lengths influence their reproductive success through within-unit and extra-unit paternities. We found that although high rank increases the likelihood of producing within-unit paternity offspring in the short term, tenure length is a stronger determinant of long-term reproductive success via both within-unit and extra-unit paternities. Females may gain direct benefits from producing extra-pair paternity offspring by reducing the risk of infanticide through mating with all-male band males and/or by selecting high-ranking leader males for better access to resources. Moreover, females may also accrue additional indirect benefits from producing extra-pair paternity offspring when more adult males are available in the breeding band. Our findings highlight extra-pair paternity as a reproductive strategy for both male and female golden snub-nosed monkeys to optimize reproductive success, which may also play a role in maintaining stability in this complex primate society.