There is still a need to analyze the factors that enhance navigation accuracy. This study aims to examine how success in environment learning relates to task goals and WM. A total of 90 undergraduates (46 females) learned a route from a virtual navigation experience after being given a goal that involved tracing the route (a route-based goal) or finding a shortcut (a survey-based goal). The two groups thus formed were each divided into three subgroups according to the dual-task paradigm: one only navigated (control condition); the other two did so while simultaneously performing a visuo-spatial or verbal secondary task. Afterwards, participants traced the previously seen route and found a shortcut. Several visuo-spatial and verbal WM tasks were also administered. The results showed that participants given a route-based goal performed better in the route-tracing task; and those given a survey-based goal were better at finding shortcuts. An influence of WM was also shown: higher WM (visuo-spatial and verbal) ability significantly reduced the number of route-tracing errors made while performing a secondary visuo-spatial task, regardless of the goal, whereas no such effects emerged for shortcut finding. These results offer new insight on how task goals and WM support successful navigation.