Spatial navigation is one of the fundamental cognitive functions central to survival in most animals. Studies in humans investigating the neural foundations of spatial navigation traditionally use stationary, desk-top protocols revealing the hippocampus, parahippocampal place area (PPA), and retrosplenial complex to be involved in navigation. However, brain dynamics, while freely navigating the real world remain poorly understood. To address this issue, we developed a novel paradigm, the AudioMaze, in which participants freely explore a room-sized virtual maze, while EEG is recorded synchronized to motion capture. Participants (n = 16) were blindfolded and explored different mazes, each in three successive trials, using their right hand as a probe to “feel” for virtual maze walls. When their hand “neared” a virtual wall, they received directional noise feedback. Evidence for spatial learning include shortening of time spent and an increase of movement velocity as the same maze was repeatedly explored. Theta-band EEG power in or near the right lingual gyrus, the posterior portion of the PPA, decreased across trials, potentially reflecting the spatial learning. Effective connectivity analysis revealed directed information flow from the lingual gyrus to the midcingulate cortex, which may indicate an updating process that integrates spatial information with future action. To conclude, we found behavioral evidence of navigational learning in a sparse-AR environment, and a neural correlate of navigational learning was found near the lingual gyrus.