In chacma baboons (Papio hamadryas ursinus), adult males and lactating females form preferential associations, or 'friendships', that provide protection against potentially infanticidal attacks. Little is known about the mechanisms by which males and females form friendships, or the function of friendships for males. We examined the relationship between mating activity, paternity and friendships over a 3-year period. A male's proportion of consort activity with a female within and outside of her period of most likely conception, along with his dominance rank, each contributed importantly in models of paternity outcomes and formation of friendships. In 87% of births, the male that monopolized the greatest proportion of a female's consort days during her last conceptive cycle was the father of her offspring. In 82% of the births where the female's primary consort partner was present at parturition, he became her friend. When the primary consort partner was absent at parturition, females formed friendships with males that had monopolized the second or third greatest proportion of their previous consort days. Similarly, 78% of males became friends with females with whom they had obtained their greatest consort success. Such a flexible strategy based on probabilistic assessment of paternity may be adaptive for females, given unpredictable fluctuations in male presence within the group. In a mating system with high dominance-based reproductive skew, males may benefit by investing preferentially in those infants that they are most likely to have fathered.