Navigation instructions in pre- and on-trip routing services are usually based on street names and types, distances, and turn directions. However, in digital street graphs it is common that street names for separately mapped pedestrian and cycle links are missing. This leads to unsatisfactory instructions containing “unknown road” records. Often, these unnamed links run parallel to a named road, and it would be beneficial to use this information to generate instructions similar to “follow the sidewalk along Street A”, whereby “Street A” has to be determined by an algorithm. This paper introduces the Unnamed Link Naming Problem (ULNP) and presents a new approach to automatically extract suitable names to describe separately mapped pedestrian and cycle links. The approach has been tested using OpenStreetMap data and manually generated ground truth data for the second district of the city of Vienna, Austria. Results show that our best method achieves 90.7% correct matches in this challenging setting.