Fractal geometry has been used to describe natural and built environments, but has yet to be studied in navigational research. In order to establish a relationship between the fractal dimension (D) of a natural environment and humans' ability to navigate such spaces, we conducted two experiments using virtual environments that simulate the fractal properties of nature. In Experiment 1, participants completed a goal-driven search task either with or without a map in landscapes that varied in D. In Experiment 2, participants completed a map-reading and location-judgment task in separate sets of fractal landscapes. In both experiments, task performance was highest at the low-to-mid range of D, which was previously reported as most preferred and discriminable in studies of fractal aesthetics and discrimination, respectively, supporting a theory of visual fluency. The applicability of these findings to architecture, urban planning, and the general design of constructed spaces is discussed.