As public and commercial facilities grow in scale and complexity, wayfinding within such environments has become an increasingly challenging task. Conventional aids, such as floor guides, are often insufficient because their fixed locations and limited accessibility, particularly for foreign visitors navigating multilingual signage. This study investigates the potential of wall decorations as continuous, language-independent visual cues to support pedestrian navigation. In the first phase, ten participants evaluated the memorability of eight types of three-dimensional wall decorations in a virtual environment. Decorations featuring identifiable motifs were determined to be more naturally recallable. In the second phase, 18 participants performed wayfinding tasks in virtual mazes simulating a three-story hotel, with the conditions varying according to the presence and type of wall decorations. The results indicated significantly shorter return journey times in environments with naturally recallable decorations (p < .001), suggesting enhanced spatial memory. Participants under these conditions relied less on alternative cues, such as room numbers or route features. Qualitative feedback emphasized the importance of decoration distinctiveness and density. These findings suggest that strategically designed wall decorations can serve as effective navigational aids, enhancing route memory and supporting intuitive movement in complex architectural spaces.