The advance of GPS-enabled devices facilitates people to record their location histories with GPS traces, which imply human behaviors and preferences related to travel. In this paper, we perform two types of travel recommendations by mining multiple users’ GPS traces. The first is a generic one that recommends a user with top interesting locations and travel sequences in a given geospatial region. Here, interesting locations mean the culturally important places, such as Tiananmen Square in Beijing, and frequented public areas, like shopping malls and restaurants. The second is a personalized recommendation that provides an individual with locations matching her travel preferences. To achieve the first recommendation, we model multiple users’ location histories with a tree-based hierarchical graph (TBHG). Based on the TBHG, we propose a HITS (Hypertext Induced Topic Search)-based inference model, which regards an individual’s access on a location as a directed link from the user to that location. This model infers two values, the interest level of a location and a user’s travel experience, by taking into account 1) the mutual-reinforcement relation between the two values and 2) the geo-region conditions. Considering the inferred values, we mine the classical travel sequences among locations. In the personalized recommendation, we first understand the correlation among locations in terms of 1) the sequences that the locations have been visited and 2) the travel experiences of the persons accessing these locations. Beyond the geo-distance relation, this correlation represents the relation between locations in the spaces of human behavior. Later, we incorporate the location correlation into a collaborative filtering (CF)-based model that infers a user’s interests in an unvisited location based on her locations histories and that of others. We evaluated our system based on a real-world GPS trace dataset collected by 107 users over a period of one year. As a result, our HITS-based inference model outperformed baseline approaches like rank-by-count and rank-by-frequency. Meanwhile, when considering the users’ travel experiences and location interests, we achieved a better performance in recommending travel sequences beyond baselines including rank-by-count and rank-by-interest. Regarding the personalized recommendation, our approach is more effective than the weighted Slope One algorithm with a slightly additional computation. In addition, in contrast to the Pearson correlation-based CF model, our method is much more efficient while keeping the similar effectiveness.