A navigation device and a guide route search method prevents searching for a detour route, and shortens the time required for setting an eventual guide route. A first partial route is extracted from a first guide route found in accordance with map data divided into three hierarchical levels, based on information about a road network. The first guide route is the route from the current location to a destination. A second partial route is obtained by performing a route search between the nodes at opposite ends of the first partial route, based on the map data containing the lowest level. A second guide route is obtained by replacing the first partial route in the first guide route with the second partial route, and is set as the eventual guide route.