Deterrence, a defender's avoidance of a challenger's attack based on the threat of retaliation, is a basic ingredient of social cooperation in several animal species and is ubiquitous in human societies. Deterrence theory has recognized that deterrence can only be based on credible threats, but retaliating being costly for the defender rules this out in one-shot interactions. If interactions are repeated and observable, reputation building has been suggested as a way to sustain credibility and enable the evolution of deterrence. But this explanation ignores both the source and the costs of obtaining information on reputation. Even for small information costs successful deterrence is never evolutionarily stable. Here we use game-theoretic modelling and agent-based simulations to resolve this puzzle and to clarify under which conditions deterrence can nevertheless evolve and when it is bound to fail. Paradoxically, rich information on defenders' past actions leads to a breakdown of deterrence, while with only minimal information deterrence can be highly successful. We argue that reputation-based deterrence sheds light on phenomena such as costly punishment and fairness, and might serve as a possible explanation for the evolution of informal property rights.