AbstractSocial evolution theory faces a puzzle: a gap between theoretical and empirical results on reciprocity. On the one hand, models show that reciprocity should evolve easily in a wide range of circumstances. On the other hand, empirically, few clear instances of reciprocity (even in a broad sense) have been found in nonhuman animals. In this paper, I aim to suggest and evaluate a novel reason concurring to solve this puzzle. I propose that it is difficult for reciprocity to evolve because it raises an evolutionary problem ofbootstrapping: it requires that two complementary functions: (i) the ability to cooperate and (ii) the ability to respond conditionally to the cooperation of others, arise together and reach a significant frequency, whereas neither of them can be favoured in the absence of the other. I develop analytical models and simulations showing that, for this reason, the evolutionary emergence of reciprocal cooperation is highly unlikely. I then discuss the consequences of this result for our understanding of cooperation.