Metaphor is central to human language and cognition. It has also been proposed to play an important role in language evolution. For these reasons, the evolution of metaphor and the cognitive processes supporting it are an important explanatory target for evolutionary accounts of human language. Here, we focus on the evolution of one particular capacity supporting metaphor, that of analogy. We integrate data from comparative psychology and cognitive archaeology to investigate the evolution of analogy as well as its evolutionary foundations. We present evidence that many aspects of analogy display evolutionary continuity between humans and non-human animals. In addition, we propose that analogical capacities can also be inferred from the archaeological record by looking at productional diversity in tool-making. Overall, we argue that analogy as an important cognitive process supporting metaphor has deep evolutionary roots.