The structure of the physical environment can have a significant influence on individuals’ ability to orient within it. We asked participants to perform a cued wayfinding task in two virtual environments to test the hypothesis that spatial orientation skills are indeed affected by the physical complexity of the environment. The two virtual environments used for testing differed solely in one objective measure of plan complexity, that is, the average number of connections at each decision point or terminal corridor. Our results showed that participants committed more errors and took longer to reach their destinations in the more interconnected environment. Performance was more efficient on trials in which participants were able to use previously learned routes relative to trials in which participants were forced to plan novel routes. These findings provide strong evidence that people’s ability to navigate in unfamiliar surroundings is affected by the layout complexity of the environment.