In recent years, a number of studies have been done on Location-Based Service (LBS) due to the wide applications. One important research issue is the tracking and prediction of users’ mobile behavior. In this paper, we propose a novel data mining algorithm named TMSP-Mine for efficiently discovering the Temporal Mobile Sequential Patterns (TMSPs) of users in LBS environments. To our best knowledge, this is the first work on mining the mobile sequential patterns associated with moving paths and time intervals in LBS environments. Furthermore, we propose novel location prediction strategies that utilize the discovered TMSPs to effectively predict the next movement of mobile users. Finally, we conducted a series of experiments to evaluate the performance of the proposed method under different system conditions by varying various parameters.