The growing complexity of website navigation demands more behavior-oriented research. Today, static and sequential menus have become virtually incompatible with adaptive forms of web layouts; tagging-based menus started to dominate; and these navigational elements more and more co-exist on webpages. Previous research compares the three basic types of menus (static, sequential, and expandable) for two dimensions: reduction of mental load (objective, linked to task complexity and structural complexity) and growth of user satisfaction (subjective, linked to menu type). Objectives. We hypothesized that growth of task complexity linked to menu complexity leads to selection of non-productive search strategies and to growth of perceived complexity of the interface. Research design. Following Kang et al. (2008), we have divided user search strategies into productive (systemic) and non-productive (chaotic) and have conducted an experimental pre-test. Menu complexity was created by using four different menus in one prototype. Structural complexity was assessed by path depth and menu options diversity. The search tasks were designed to be realizable disregarding the menu complexity. Two homogenous groups of 10 assessors were consecutively conducting tasks on six HTML pages of the prototype. A questionnaire was used to assess user satisfaction. Results. For low-complexity tasks, menu diversity has virtually no impact upon navigational behavior. But we have discovered impact of menu complexity for high-complexity tasks for multi-menu navigational schemes. Additional tests with newer types of menus show that they make the assessors drop the sequential principle of search. Also, these pages were perceived as the hardest to use.