A visiting destination prediction device includes: a user position information acquiring unit configured to acquire user position information indicating a position of a user; an action history acquiring unit configured to acquire information on an action history of the user; and a visiting POI estimating unit configured to estimate a visiting POI which is a visiting destination of the user on the basis of a relationship between an acquired user position and a previously stored POI position and a relationship between the acquired action history of the user in a predetermined period and previously stored POI relevant information.