Navigation through an environment is a fundamental human activity. Although group differences in navigational ability are documented (e.g., gender), little is known about traits that predict these abilities. Apart from a well-established link between mental rotational abilities and navigational learning abilities, recent studies point to an influence of trait anxiety on the formation of internal cognitive spatial representations. However, it is unknown whether trait anxiety affects the processing of information obtained through externalized representations such as maps. Here, we addressed this question by taking into account emerging evidence indicating impaired performance in executive tasks by high trait anxiety specifically in individuals with lower executive capacities. For this purpose, we tested 104 male participants, previously characterised on trait anxiety and mental rotation ability, on a newly-designed map-based route learning task, where participants matched routes presented dynamically on a city map to one presented immediately before (same/different judgments). We predicted an interaction between trait anxiety and mental rotation ability, specifically that performance in the route learning task would be negatively affected by anxiety in participants with low mental rotation ability. Importantly, and as predicted, an interaction between anxiety and mental rotation ability was observed: trait anxiety negatively affected participants with low—but not high—mental rotation ability. Our study reveals a detrimental role of trait anxiety in map-based route learning and specifies a disadvantage in the processing of map representations for high-anxious individuals with low mental rotation abilities.