Although kin-selection theory has been widely used to explain the tendency of individuals to bias beneficial behaviors towards relatives living within the same social group, less attention has focused on kin-biased interactions between groups. For animal societies in which females emigrate, as is the case for mountain gorillas (Gorilla beringei beringei), encounters between males in different groups often involve aggressive displays that can escalate to physical violence and fatal injuries. However, recent findings on the little-studied western gorilla (Gorilla gorilla) indicate that interactions between social groups occur more frequently than they do in mountain gorillas and are often, although not always, surprisingly nonaggressive. We investigated the pattern of genetic relationships between individuals of different groups and found evidence suggesting a previously unrecognized "dispersed male network" social structure in western gorillas in which the single males leading social groups were usually related to one or more nearby males. We propose that this provides a basis for extra-group, kin-biased behaviors and may explain the reported peaceful intergroup interactions. Furthermore, these results suggest that a patrilocal social structure, in which males remain in their natal region and potentially benefit from kin associations, is a feature unifying African apes and humans.