Many wild primates occupy large home ranges and travel long distances each day. Navigating these ranges to find sufficient food presents a substantial cognitive challenge, but we are still far from understanding either how primates represent spatial information mentally or how they use this information to navigate under natural conditions. In the course of a long-term socioecological study, we investigated and compared the travel paths of sympatric spider monkeys (Ateles belzebuth) and woolly monkeys (Lagothrix poeppigii) in Amazonian Ecuador. During several field seasons spanning an 8-year period, we followed focal individuals or groups of both species continuously for periods of multiple days and mapped their travel paths in detail. We found that both primates typically traveled through their home ranges following repeatedly used paths, or "routes". Many of these routes were common to both species and were stable across study years. Several important routes appeared to be associated with distinct topographic features (e.g., ridgetops), which may constitute easily recognized landmarks useful for spatial navigation. The majority of all location records for both species fell along or near identified routes, as did most of the trees used for fruit feeding. Our results provide strong support for the idea that both woolly and spider monkey use route-based mental maps similar to those proposed by Poucet (Psychol Rev 100:163-182, 1993). We suggest that rather than remembering the specific locations of thousands of individual feeding trees and their phenological schedules, spider and woolly monkeys could nonetheless forage efficiently by committing to memory a series of route segments that, when followed, bring them into contact with many potential feeding sources for monitoring or visitation. Furthermore, because swallowed and defecated seeds are deposited in greater frequency along routes, the repeated use of particular travel paths over generations could profoundly influence the structure and composition of tropical forests, raising the intriguing possibility that these and other primate frugivores are active participants in constructing their own ecological niches. Building upon the insights of Byrne (Q J Exp Psychol 31:147-154, 1979, Normality and pathology in cognitive functions. Academic, London, pp 239-264, 1982) and Milton (The foraging strategy of howler monkeys: a study in primate economics. Columbia University Press, New York, 1980, On the move: how and why animals travel in groups. University of Chicago Press, Chicago, pp 375-417, 2000), our results highlight the likely general importance of route-based travel in the memory and foraging strategies of nonhuman primates.