A navigation device that is provided with reference databases that include search databases that are referenced when the navigation device performs a location search for a location on a map, that accepts provided update data, and that performs update processing for the reference databases is provided with a priority processing unit that, in a case where a command to perform the location search is input during the update processing for the reference databases, gives priority to performing the update processing for location data that are stored in the search databases, as well as with a search unit that, after the update processing for the location data is completed by the priority processing unit, is enabled to perform the location search using the updated location data.