© 2017 Elsevier Ltd Despite major advances in evolutionary theories, some aspects of evolution remain neglected: whether evolution: would come to a halt without abiotic change; is unbounded and open-ended; or is progressive and something beyond fitness is maximized. Here, we discuss some models of ecology and evolution and argue that ecological change, resulting in Red Queen dynamics, facilitates (but does not ensure) innovation. We distinguish three forms of open-endedness. In weak open-endedness, novel phenotypes can occur indefinitely. Strong open-endedness requires the continual appearance of evolutionary novelties and/or innovations. Ultimate open-endedness entails an indefinite increase in complexity, which requires unlimited heredity. Open-ended innovation needs exaptations that generate novel niches. This can result in new traits and new rules as the dynamics unfolds, suggesting that evolution is not fully algorithmic.