In the present study, participants learned the locations of 12 landmarks by following a guided route either in a desktop virtual environment or on an omnidirectional treadmill paired with a virtual reality headset. Spatial learning and wayfinding efficiency were later assessed across both interface conditions. Additionally, the ratio of physical to cognitive costs for navigating to goals was manipulated across trials. Results indicated that although the two groups did not differ in spatial learning, participants navigating on treadmills selected more efficient routes than those in the desktop group in trials involving high physical cost. Higher levels of self-report cybersickness were associated with reduced spatial learning and wayfinding efficiency, independent of interface condition. These findings validate the use of omnidirectional treadmills for investigating the tradeoff between cognitive and physical effort in navigation. At the same time, reducing cybersickness is essential to ensure the effective use of this technology.