Palembang is the capital city South Sumatra Province as well as big city. For a big city, transportation is a critical issue for society as well as its tourist. This study develops an optimal route search system using A * algorithm. A * algorithm using nearest distance estimates to achieve goals and have a heuristic value that is used as a basis for consideration. The resulting software is capable of finding the optimal transportation solution in the Palembang area so that people can get information easily and the accuracy of the application by 91.8%.