When navigating, wild animals rely on internal representations of the external world to take movement decisions – called “cognitive maps”. As a rule, flexible navigation is hypothesized to be supported by sophisticated spatial skills (i.e., Euclidean cognitive maps); however, constrained movements along habitual routes is the most commonly reported navigation strategy. Even though incorporating metric information (i.e., distances and angles between locations) in route-based cognitive maps would likely enhance an animal’s navigation efficiency, there has been no evidence of this strategy reported for non-human animals to date. Here, we examine the properties of the cognitive map used by a wild population of primates by testing a series of cognitive hypotheses against spatially-explicit movement simulations. We collected 3104 hours of ranging and behavioural data on five groups of black howler monkeys (Alouatta pigra) at Palenque National Park, Mexico, from September 2016 through August 2017. We simulated correlated-random walks mimicking the ranging behaviour of the study subjects and tested for differences between observed and simulated movement patterns. Our results indicated that black howler monkeys engaged in constrained movement patterns characterized by a high path recursion tendency, which limited their capacity to travel in straight lines and approach feeding trees from multiple directions. In addition, we found that the structure of observed route networks was more complex and efficient than simulated route networks, suggesting that black howler monkeys incorporate metric information into their cognitive map. Our findings not only expand the use of metric information during route navigation to non-human animals but also highlight the importance of considering efficient route-based navigation as a cognitively demanding mechanism.