A system and method for providing destination recommendations to a user based on mining of a location history. The location history provides information on locations visited by users of the system over time. The system mines the location history to identify location pairs. Each location pair comprises an originating location visited by a user and a next location that was visited by the user within a defined time threshold of visiting the originating location. The system aggregates location pairs by common originating location. The system then takes into account the current location of a requesting user. The system uses the current location information to identify a corresponding originating location in a location history index. The system provides recommendations based at least in part on how frequently certain next locations were visited after visiting the originating location.