This experiment investigated the role of familiarity, map usage and instruction on wayfinding strategies and performance. 32 participants had to find eight goals in a multilevel building ensemble consisting of two distinctive vertical segments. Generally users who were familiar with the building ensemble outperformed first-time visitors of the setting. We tested if the standard wall-mounted floor maps found in the majority of public buildings can help navigation in a complex unknown environment. Unfamiliar users tried to make use of these plans more frequently, but were not able to compensate for spatial knowledge deficits through them. Two strategies of across-level wayfinding are compared with respect to a region-based hierarchical planning approach. Strategy selection relied largely on task and instruction characteristics. Overall, the strategy of moving horizontally into the target section of the building prior to vertical travel was shown to be more effective in this multi-building setting.