Rich information environments such as online tutorials and web-books pose considerable difficulties for users, of which the most notable is being ‘lost in hypertext’. If these environments are to become commonplace, they must be designed to relieve users of these difficulties. In this paper we study the effects of dynamic navigational maps on orientation and search performance. We designed a conceptual map that tracks the user’s position vis-à-vis the content of the web-book and the history of the user’s visits. We show how these maps improve search performance significantly in terms of efficiency (number of clicks) but only weakly in terms of time or accuracy. We call for more research on how to enhance user control in complex information environments.