A route searching device, comprising, a map data storage unit (3, 6) adapted to store map data including a road link, a route searching unit adapted to retrieve routes from a current position to a destination by using the road link stored in the map data storage unit (3, 6), a deviation judging unit (1, 101) adapted to determine whether or not traveling is performed with deviation from an original route retrieved by the route searching unit, a deviation information storage unit adapted to store, when the deviation judging unit determines that deviation from the original route occurs at a first road intersection, a road link relating to a position of the first road intersection deviating from the original route, a road link relating to a position of a second road intersection returning to the original route and a deviation route traveled from the first road intersection to a point of return to the original route at the second road intersection, the deviation information storage unit arranged to store: as the road link relating to the position deviating from the original route, a link just before deviation being a link just before deviating from the original route retrieved by the route searching unit; and as the road link relating to the position returning to the original route,a link just after returning to the original route retrieved by the route searching unit, and a route replacement unit adapted to replace at least a part of the original route retrieved by the route searching unit, with the route stored in the deviation information storage unit, the route replacement unit arranged to perform replacement of the original route in the case where the link just before deviation and the link just after returning are included in the route retrieved by the route searching unit, the route searching device characterized in that: the deviation information storage unit is configured to store the route traveled with deviation in association with a replacement priority, the route replacement unit is arranged to perform replacement by prioritizing the route with one having a higher replacement priority; and the deviation information storage unit is adapted to raise the replacement priority of the route traveled with deviation in the case where a route traveled, under a condition that a route retrieved by the route searching unit is not set, includes a route corresponding to the route traveled with deviation being stored in the deviation information storage unit. as the road link relating to the position deviating from the original route, a link just before deviation being a link just before deviating from the original route retrieved by the route searching unit; and as the road link relating to the position returning to the original route,a link just after returning to the original route retrieved by the route searching unit, and the deviation information storage unit is configured to store the route traveled with deviation in association with a replacement priority, the route replacement unit is arranged to perform replacement by prioritizing the route with one having a higher replacement priority; and the deviation information storage unit is adapted to raise the replacement priority of the route traveled with deviation in the case where a route traveled, under a condition that a route retrieved by the route searching unit is not set, includes a route corresponding to the route traveled with deviation being stored in the deviation information storage unit.