As the number of people suffering from visual impairments continuously increases, there is strong need for efficient sensory substitution devices, that can support creating a rich mental spatial depiction of the environment. The use of the auditory sense has proved to be an effective approach towards creating a method of interaction with the elements of the surrounding space in a way which resembles the natural 3D visual representation of normal sighted people. Training is an essential component in the process of employing an auditory-based visual substitution device for blind people, as it helps them to learn and become proficient to process and decode the audio information and convert it into spatial mental representation. Taking into account the well-known advantages of game based learning, we propose a new method of training, consisting in a navigational 3D audio-based game. In this exploratory, goal-directed application, the player has to perform route-navigational tasks under different conditions, with the purpose of training and testing their orientation and mobility skills, relying exclusively on the perception of 3D audio cues. Experimental results showed that this game-based learning strategy leads to substantial improvements and can be a starting point for developing more enhanced sound-based navigational applications. The ludic-oriented, motivational training approach achieved straightforward immersion and concentration on the cognitive depiction of the environment, ensuring behavioral gains in the sound-directed spatial orientation.