In general, a conventional vehicle navigation apparatus is designed to navigate from a current position to a destination set up by a user. Meanwhile, the conventional vehicle navigation apparatus has been known to be constructed to record, on a recording medium, information representing a number of times and conditions of arrival to respective past arrived positions for the purpose of setting priorities for the respective past arrived positions on the basis of the recorded information, and estimating a destination from the past arrived positions on the basis of the set priorities, even if a destination is not set (see for example Patent Document 1).