Stress impairs wayfinding efficiency by reducing flexible use of shortcut strategies, highlighting the need for training methods that build resilience to stress during navigation. Drawing on theories of encoding specificity, context-dependent memory, and habitual stress training, this study examined whether stress exposure during environmental learning fosters resilience to stress in subsequent navigation or impairs learning. Eighty participants were randomly assigned to learn the layout of a desktop virtual environment, either without stress (controls) or under stress induced by threatening music, black fog, and obstructive walls. During learning, Trans-Radial Electrical Bioimpedance Velocimetry (TREV) was used to measure participants’ physiological response (heart contractility). Configural knowledge of the environment was assessed after learning, followed by 24 wayfinding trials in an immersive virtual environment, half of which included the same stressors as the learning phase. The stress exposure group acquired less environmental knowledge and were less successful at wayfinding, indicating learning impairment. However, prior stress exposure reduced perceived stress during subsequent wayfinding under stress and mitigated the negative impact of high spatial anxiety on navigation efficiency, suggesting psychological and partial behavioral resilience. Although the stress manipulation did not elicit a physiological change detectable by TREV, baseline physiological responses were associated with other stress indicators and wayfinding success. These results suggest stress exposure during learning may reduce psychological stress and enable high-anxiety individuals to better cope with navigation under stress.