The apparent rarity of contingent cooperation in animals has convinced many investigators that such reciprocity is unimportant, stimulating consideration of alternative explanations for cooperation, such as by-product mutualism and biological markets motivated by the likelihood of immediate reward. Nevertheless, there is also limited evidence that animals do sometimes rely on memory of recent interactions when behaving altruistically toward others. Here we describe a playback experiment conducted on wild female baboons, suggesting that contingent cooperation may occur among unrelated individuals, even when there is a temporal delay between the two cooperative acts. Hearing the recruitment call of an unrelated recent grooming partner caused subjects to move in the direction of the loudspeaker and approach their former partner, particularly when this partner had an infant. When the subject and her partner were close kin no such effect was observed. Subjects' responses were not influenced by any type of recent interaction, because prior grooming and prior aggression influenced their behavior in qualitatively different ways. Similarly, their responses were not prompted only by the motivation to resume friendly interactions, because prior grooming alone did not elicit approach. Instead, subjects were most likely to approach their former grooming partner when they had also heard her recruitment call. Results suggest that at least some forms of cooperation in animals may be based on memory of specific recent interactions.