There are known individual differences in both the ability to learn the layout of novel environments and the flexibility of strategies for navigating known environments. However, it is unclear how navigational abilities are impacted by high-stress scenarios. Here we used immersive virtual reality (VR) to develop a novel behavioral paradigm to examine navigation under dynamically changing situations. We recruited 48 participants (24 female; ages 17-32) to navigate a virtual maze (7.5 m × 7.5 m). Participants learned the maze by moving along a fixed path past the mazes landmarks (paintings). Subsequently, participants experienced either a non-stress condition, or a high-stress condition tasking them with navigating the maze. In the high-stress condition, their initial path was blocked, the environment was darkened, threatening music was played, fog obstructed more distal views of the environment, and participants were given a time limit of 20 s with a countdown timer displayed at the top of their screen. On trials where the path was blocked, we found self-reported stress levels and distance traveled increased while trial completion rate decreased (as compared to non-stressed control trials). On unblocked stress trials, participants were less likely to take a shortcut and consequently navigated less efficiently compared to control trials. Participants with more trait spatial anxiety reported more stress and navigated less efficiently. Overall, our results suggest that navigational abilities change considerably under high-stress conditions.