Self-localization and wayfinding are challenging tasks for people with visual impairments (PVIs), severely impacting independent mobility. Visual “You-are-here” (YAH) maps are useful for assisting local wayfinding of sighted users. They are used to self-localize and display points of interest, landmarks and routes in the surroundings. However, these maps are not always available and rarely accessible to PVIs. Relying on an iterative participatory design process with eight end-users with visual impairments, we created a proof of concept of a mobile audio-vibratory YAH map. Our design is based on either a tablet or a smartphone to ensure a small and portable solution. A user study with ten PVIs showed that the audio-vibratory YAH map that we designed provides the user with a good understanding of the surroundings and wayfinding cues. Surprisingly, the results show that the audio-vibratory YAH map prototype was as usable as the control condition (audio-tactile YAH map with a tactile overlay), with similar user satisfaction and cognitive load. A follow-up field study with two participants showed the effectiveness of the prototype for assisting in crossroad understanding. To conclude, our innovative design of a mobile audio-vibratory YAH map can overcome the portability and printing issues associated with tactile overlays and can be an appropriate solution for assisting the pedestrian navigation of PVIs.