In recent years, a number of studies have been done on Location-Based Service (LBS) due to their wide range of potential applications. In this paper, we propose a novel data mining algorithm named Cluster-based Mobile Sequential Pattern Mine (CMSP-Mine) for efficiently discovering the Cluster-based Mobile Sequential Patterns (CMSPs) of users in LBS environments. In CMSP-Mine, we first propose a transaction similarity measurement named Location-Based Service Alignment (LBS-Alignment) to evaluate the similarity between two mobile transaction sequences. Then, we propose a transaction clustering algorithm named Cluster-Object based Smart Cluster Affinity Search Technique (CO-Smart-CAST) to form a user cluster model of the mobile transactions based on LBS-Alignment. Furthermore, we proposed the novel prediction strategy that utilizes the discovered CMSPs to precisely predict the next movement of mobile users. To our best knowledge, this is the first work on mining the mobile sequential patterns associated with moving path and user clusters in LBS environments. Finally, through a series of experiments, our proposed methods were shown to deliver excellent performance in terms of efficiency, accuracy and applicability under various system conditions.