One explanation for how people can plan efficiently despite limited cognitive resources is that we possess a set of adaptive planning strategies and know when and how to use them. But how are these strategies acquired? While previous research has studied how individuals learn to choose among existing strategies, little is known about the process of forming new planning strategies. In this work, we propose that new planning strategies are discovered through metacognitive reinforcement learning. To test this, we designed an experiment to investigate the discovery of new planning strategies. We then presented metacognitive reinforcement learning models and demonstrated their capability for strategy discovery as well as show that they provided a better explanation of human strategy discovery than alternative learning mechanisms. However, when fitted to human data, these models exhibited a slower discovery rate than humans, leaving room for improvement.