The evolutionary mechanisms of cooperation are well-studied, yet what motivates individuals to cooperate remains unclear. Although conventionally associated with enhanced social tolerance (self-domestication hypothesis) and prosociality (cooperative-breeding hypothesis), individuals belonging to species that are neither self-domesticated nor cooperatively-breeding also cooperate. An overarching interdependency hypothesis posits that inter-individual dependencies promote cooperation, but comparative evidence is lacking. We experimentally studied cooperation, prosociality, and tolerance in six macaque species along a \'despotic-egalitarian\' gradient. Within-group cooperation was higher in despotic than egalitarian societies yet restricted to few partners. Prosociality, kinship, and tolerance positively predicted cooperation success. Agent-based models consistently showed that despotic societies have fewer but more stable social bonds and, thus, higher interdependencies than egalitarian ones. Our results suggest that interdependencies facilitate the emergence and maintenance of cooperation.