Landmarks, objects in the environment used for orientation, navigation and the formation of cognitive maps are often represented in maps as pictograms. In order to support these tasks effectively and efficiently, landmark pictograms also need to be salient, as the map user needs to identify and process them quickly and easily. Two additional relevant characteristics for the usability of landmark pictograms are their meaningfulness and recognition performance. Meaningfulness is required to understand which categories of objects are represented by the pictograms. Ease of recognition prevents the necessity to consult a map repetitively and may support the formation of a cognitive map of the environment. In the present study, we investigated the relation between salience, meaningfulness and recognition performance of OpenStreetMap (OSM) pictograms and the potential effects of the visual complexity of pictograms on these usability characteristics. Salience was measured via eye fixations on specific pictograms, meaningfulness with an explicit continuous scale and recognition performance with a yes/no recognition memory paradigm. Statistical analyses showed that pictograms drew more visual attention if they were visually complex or if their meaning was inapprehensible or ambiguous. Less apprehensible pictograms were also recognized more often. Interestingly, the data indicated that longer fixations could lead to worse recognition performance. Long fixations on a pictogram may increase the likelihood of false recognition in subsequent situations where the pictogram is no longer valid or relevant. Based on the findings, we suggest balancing the meaningfulness and visual complexity of contiguous pictograms to enhance their recognition and to provide an optimal level of salience of single objects.