This paper reports on a study that compares three different methods of travel in a complex, multi-level virtual environment using a between-subjects design. A real walking travel technique was compared to two common virtual travel techniques. Participants explored a two-story 3D maze at their own pace and completed four post-tests requiring them to remember different aspects of the environment. Testing tasks included recall of objects from the environment, recognition of objects present and not present, sketching of maps, and placing objects on a map. We also analyzed task completion time and collision data captured during the experiment session. Participants that utilized the real walking technique were able to place more objects correctly on a map, completed the maze faster, and experienced fewer collisions with the environment. While none of the conditions outperformed each other on any other tests, our results indicate that for tasks involving the naive exploration of a complex, multi-level 3D environment, the real walking technique supports a more efficient exploration than common virtual travel techniques. While there was a consistent trend of better performance on our measures for the real walking technique, it is not clear from our data that the benefits of real walking in these types of environments always justify the cost and space trade-offs of maintaining a wide-area tracking system.