Innovative behaviour in animals, ranging from invertebrates to humans, is increasingly recognized as an important topic for investigation by behavioural researchers. However, what constitutes an innovation remains controversial, and difficult to quantify. Drawing on a broad definition whereby any behaviour with a new component to it is an innovation, we propose a quantitative measure, which we call the magnitude of innovation, to describe the extent to which an innovative behaviour is novel. This allows us to distinguish between innovations that are a slight change to existing behaviours (low magnitude), and innovations that are substantially different (high magnitude). Using mathematical modelling and evolutionary computer simulations, we explored how aspects of social interaction, cognition and natural selection affect the frequency and magnitude of innovation. We show that high-magnitude innovations are likely to arise regularly even if the frequency of innovation is low, as long as this frequency is relatively constant, and that the selectivity of social learning and the existence of social rewards, such as prestige and royalties, are crucial for innovative behaviour to evolve. We suggest that consideration of the magnitude of innovation may prove a useful tool in the study of the evolution of cognition and of culture.