We consider the evolution of cognition and the emergence of creative behaviour, in relation to vocal communication. We address two key questions: (i) what cognitive and/or social mechanisms have evolved that afford aspects of creativity?; (ii) has natural and/or sexual selection favoured human behaviours considered 'creative'? This entails analysis of 'creativity', an imprecise construct: comparable properties in non-humans differ in magnitude and teleology from generally agreed human creativity. We then address two apparent problems: (i) the difference between merely novel productions and 'creative' ones; (ii) the emergence of creative behaviour in spite of high cost: does it fit the idea that females choose a male who succeeds in spite of a handicap (costly ornament); or that creative males capable of producing a large and complex song repertoire grew up under favourable conditions; or a demonstration of generally beneficial heightened reasoning capacity; or an opportunity to continually reinforce social bonding through changing communication tropes; or something else? We illustrate and support our argument by reference to whale and bird song; these independently evolved biological signal mechanisms objectively share surface properties with human behaviours generally called 'creative'. Studying them may elucidate mechanisms underlying human creativity; we outline a research programme to do so.