From learning to play video games to using novel tools, humans are able to acquire a variety of complex mappings between their actions and arbitrary outcomes. In addition, once they have learned such mappings, they often have to use them sequentially to achieve goals, i.e., planning. In this work we study how the learning of a novel mapping interacts with planning in the context of grid navigation. In order to do so, we developed a computer-based game where subjects have to move a cursor from start to target locations using the keys of their keyboard. Importantly, to more closely resemble the complexity of the mappings that people acquire in their lives, the cursor movement was determined by a non-trivial rule inspired by the movement of the piece of chess known as the Knight. In Experiment 1, we show that participants were able to improve their performance in our task, though not arriving optimally to the targets in the majority of trials. Additionally, we assessed three cognitive models and found that a model that includes Bayesian mapping-learning, path search and habit formation components described participants data better. Finally, in Experiment 2, we showed that exposing participants to the mapping component of the task without having to plan, provides a performance improvement when exposed to the full task later. Crucially, this improvement does not occur if subjects are exposed to the planning component of the task prior to doing it fully. Overall, these results suggest that in order for planning processes to be effectively deployed, the mapping of actions should be learned first.