To improve accuracy of determining whether route elements stored as a history are route elements familiar to the user, a navigation apparatus 100 includes: a passage history storage unit 9a that stores a history of route elements passed in the past; a memory cost determination unit 84 that determines memory costs indicative of how less likely a user still has in mind the route elements stored in the passage history storage unit 9a based on the history stored in the passage history storage unit 9a; a route search unit 85 that searches for a route leading to a destination by combining the route elements to minimize a route cost of the entire route including the memory costs determined by the memory cost determination unit 84; and a navigation unit 86 that performs a route guide in accordance with the route searched by the route search unit 85.