There is provided a vehicle navigation system for searching predetermined information after map data is updated and navigating a user more effectively even when the user only knows information before the update. The vehicle navigation system includes a control section; a map data read section for reading first map data from a map database; a map data acquisition section for acquiring second map data for update; a map data update section for generating updated map data by using the first map data and the second map data; and a history information management section for managing a search result, a travel route or the like, which the user obtained by specifying search conditions, as history information, wherein the map data update section generates the updated map data so as to associate the first map data, which is associated with the history information, together with the second map data.