Outdoor navigation of visually impaired people most often is based on data from the GPS maps and Geographic Information Systems (GIS). Such systems cannot be used for navigation in the regions where there are not any GPS maps or the maps are not sufficiently precise and detailed. This article describes an algorithm for real-time GPS track simplification. The test results show that the proposed algorithm (RSTS) has efficiency similar to the Douglas–Peucker algorithm, which is regarded as the best for track simplification. The reduction of the number of points in different transportation modes, while keeping the shape of the route, is over 90%. The size of the file describing the track is reduced more than 30 times. The algorithm finds the critical points of the route. This allows for navigation along the track so conversion of track to route is not needed. The algorithm is part of a low cost and widely accessible Java 2 Mobile Edition (J2ME) application for navigation of visually impaired.