Mammals commonly avoid mating with maternal kin, probably as a result of selection for inbreeding avoidance. Mating with paternal kin should be selected against for the same reason. However, identifying paternal kin may be more difficult than identifying maternal kin in species where the mother mates with more than one male. Selection should nonetheless favour a mechanism of paternal kin recognition that allows the same level of discrimination among paternal as among maternal kin, but the hypothesis that paternal kin avoid each other as mates is largely untested in large mammals such as primates. Here I report that among wild baboons, Papio cynocephalus, paternal siblings exhibited lower levels of affiliative and sexual behaviour during sexual consortships than non-kin, although paternal siblings were not significantly less likely to consort than non-kin. I also examined age proximity as a possible social cue of paternal relatedness, because age cohorts are likely to be paternal sibships. Pairs born within two years of each other were less likely to engage in sexual consortships than pairs born at greater intervals, and were less affiliative and sexual when they did consort. Age proximity may thus be an important social cue for paternal relatedness, and phenotype matching based on shared paternal traits may play a role as well.