This chapter presents a theory of natural creativity and its relation to certain features of intelligence and cognitive faculties. To test the theory we employ simulated worlds of varying complexity, inhabited by creatures with a genetically-evolving mental model. Plan-making strategies are compared between creatures in each of these worlds. The results show that creative behaviors are governed by the world’s structural coherence and complexity. In light of the results we present a new definition of creativity, propose a theory for why creativity evolves in nature, and discuss creativity’s relation to perception, goals, logic, understanding, and imagination. Creativity has been a difficult concept to define and its exact relationship with intelligence remains to be explained. The theoretical framework presented is proposed as a foundation and tool for furthering understanding of natural creativity and to help develop creative artificially intelligent systems.