An important activity in urban three-dimensional (3D) mobile navigation is browsing the buildings in the environment and matching them to those in the 3D city map. There are different factors affecting the recognition process such as changes in the appearances of buildings, weather, and illumination conditions. The current aim was to study the salience of different types of visual cues in the recognition of buildings in 3D maps in suboptimal conditions. A pilot laboratory experiment was conducted, in which test participants recognized buildings in a 3D city map using systematically prepared photographs as stimuli, and their cognitive processes were studied using the think aloud protocol. The results suggested that buildings in a 3D city map can be recognized based on a variety of different visual cues ranging from small details such as textual signs to the shape of the building and landmark features such as towers. The results also suggested that buildings are recognized relatively much based on their location and other buildings and objects in their surroundings.