We investigated male social relationships in 2 groups of black howlers (Alouatta pigra) in Palenque National Park, Mexico, over a 14-mo study characterized by frequent changes in male group membership. Both single males and pairs of males entered our focal groups. Single males tended to join groups, whereas pairs of males entering groups together successfully evicted resident males. The 19 male dyads across the 11 periods defined by changes in group membership were rarely in close proximity or interacting with one another. Nevertheless, 1 male formed significantly closer associations with resident females in 6 periods and achieved higher mating success during 4 of the periods when ≥1 female was sexually active. In the other 5 periods, no particular male maintained significantly closer associations with resident females, which may be a result of the rapid sequence of changes in male membership and corresponding social instability. Resident males participated frequently and consistently in mutual howling, but the resident male with the strongest female associations and highest mating success initiated howling bouts more frequently in all but 1 of the 6 socially stable periods. Though still preliminary, our findings suggest that variation in social relationships among male black howlers may be more related to their ability to establish strong relationships with females than to their relationships with one another.