Today, anyone feeling lost in a city or unsure about how to navigate can use navigation services to look up routes to where they want to go. Current research investigating these services has primarily focused on how to find an appropriate route and how to best support navigation along it, and not how routes and the maps they are presented on are perceived. What makes one route look more difficult to navigate than another? And how does experience with using navigation services and maps in daily life influence how difficult a route is perceived to be? We explored these questions in a survey study where participants rated the perceived difficulty of pedestrian routes in ten different cities. The results show that routes in more complex urban environments were perceived as more complex than routes in easier environments. At least partly, perceived difficulty seems to follow earlier conceptualizations of route complexity, but open questions remain regarding the interplay of environmental structure, route properties, and the map representation.