Evolutionary algorithms frequently get stuck on local optima and fail to find the global optimum when local gradients do not point the search process toward the direction of the global optimum. A recent breakthrough called Novelty Search ameliorates this problem by enabling the search process to explore in every direction by encouraging the production of novel, or not-yet-seen, phenotypes (e.g. new robot behaviors). However, a problem with Novelty Search is that it can get lost on "novelty plateaus" wherein novel behaviors in offspring are not immediately produced by mutation and crossover (e.g. when a sequence of specific mutations is required to produce new behaviors, but the intermediate mutations are not rewarded because they do not produce novel behaviors). In such cases, Novelty Search and related approaches that reward behavioral diversity can get stuck. Here we introduce a new approach, borrowed from human psychology, that mitigates this problem: encouraging creative thinking. In addition to rewarding novel behavior, we encourage evolving neural networks to "think differently" by rewarding not-yet-seen firing patterns in hidden neurons, which we call the "Creative Thinking Approach." We hypothesize that encouraging novel thinking can reward stepping stones toward new behaviors. On a variety of challenging robotic control problems from previous publications we demonstrate that, as problem difficulty increases, adding the Creative Thinking Approach increasingly improves performance over simply encouraging novel behaviors. Our results suggest that the Creative Thinking Approach could help improve the scale and complexity of problems that can be solved by evolutionary algorithms.