Four audial navigation structure conditions, designed to support a voice messaging service, each demanding a different degree of cognitive load, were assessed by 40 naive subjects in groups of 10. Three were voice-controlled: Hierarchical, Flexible (direct, no menus) and Guided (Yes/No) and one was keypad-controlled: hierarchical. Voice recognition was simulated by means of a Wizard-of-Oz set-up. The four subject groups were matched regarding spatial ability (High/ Low) as measured by the Duremann-Salde battery. Initial interaction performance was observed over six tasks, without providing the subjects with a conceptual model of the navigation structure or an appropriate command syntax. Neither number of completed tasks (4.6-5.1 out of 6), total completion time (701-849 s), nor subjective attitudes differed significantly across navigation conditions. The simple optimum path measure was significant, favouring the guided (4.1 out of 6) as compared to the flexible structure (2.5 out of 6). A significant interaction effect between total completion time and spatial ability was found. Subjects scoring high on spatial ability obtained shorter task completion time than those scoring low, except for the guided structure, where the opposite effect occurred. The results stress the importance of adapting navigating structure to specific user abilities for user environments such as telephone services. A highly guided navigation style, a structure that maximizes optimum path score, suits users with low spatial ability, especially in the initial learning phase.