Innovation – the process that generates novel learned behaviours – is a defining feature of intelligence, and has long attracted the interest of scientists for its implications in brain evolution, emergence of culture, and adaptation to environmental changes. Although most animals have the capacity to innovate, only a few excel in their innovative capacities. A salient feature of these animals is a highly encephalized brain, which provides the cognitive basis for complex behaviors. Highly innovative animals also tend to be ecological generalists, long-lived and sociable, features that are thought to enhance the payoff of innovation. The evolutionary origin of innovative abilities is unclear, however, because innovating implies coping with problems the animal has not experienced before. A possibility is to consider innovation as an emergent property that results from the combination of cognitive and noncognitive traits that have coevolved as part of a life-history syndrome to cope with environmental changes. The coevolution of innovation and social learning capacities is particularly relevant because it has facilitated the accumulation of the knowledge needed for more complex behaviours. The ability to socially transmit knowledge may thus be behind the exceptional variety and sophistication of human innovations.