We modified classical mental exploration task introducing verbal modality. Consequently, we could test robust effects from lexical processing in an attempt to understand whether the underlying mental representation is strictly propositional. In our three experiments, in addition to map modality (visual or verbal), lexical frequency, concreteness and visual frequency were also varied. The symbolic distance effect was replicated, regardless of map modality. Exploration of distances was regularly faster on pictorial maps. Effects of lexical frequency and concreteness were not significant for verbal maps. However, when visual frequency was introduced on pictorial maps both type of frequencies generated measurable effects. Our findings directly contradict the assumptions of propositional theories (1) subjects were faster in the visual modality, which would be difficult to explain if the perceptual code had to be transformed into propositional, (2) word frequency and concreteness did not contribute as would be expected if propositional code were a default.