Embodiments that relate to head-mounted computing device for providing navigation assistance via audio output are disclosed. For example, in one disclosed embodiment depth image and visible image data are used to generate a three-dimensional mesh of at least a portion of an environment. Using the mesh, at least one feature in the environment is detected. When operating in a familiar navigation mode and based on detecting the feature, a first audio navigation cue is outputted to the user. When operating in an unfamiliar navigation mode and based on detecting the feature, a second audio navigation cue is outputted to the user, where the second audio navigation cue differs from the first audio navigation cue.