Indoor localization and navigation systems for individuals with visual impairments typically rely upon extensive augmentation of the physical space, significant computational resources, or heavy and expensive sensors; thus, few systems have been implemented on a large scale. This work describes a system able to guide people with visual impariments through indoor environments using inexpensive sensors, such as accelerometers and compasses, which are available in portable devices like smart phones. The method takes advantage of feedback from the human user, who confirms the presence of landmarks, something that users with visual impairments already do when navigating in a building. The system calculates the user’s location in real time and uses it to provide audio instructions on how to reach the desired destination. Initial early experiments suggested that the accuracy of the localization depends on the type of directions and the availability of an appropriate transition model for the user. A critical parameter for the transition model is the user’s step length. Consecutively, this work also investigates different schemes for automatically computing the user’s step length and reducing the dependence of the approach on the definition of an accurate transition model. In this way, the direction provision method is able to use the localization estimate and adapt to failed executions of paths by the users. Experiments are presented that evaluate the accuracy of the overall integrated system, which is executed online on a smart phone. Both people with visual impairments and blindfolded sighted people participated in the experiments, which included paths along multiple floors that required the use of stairs and elevators.