Abstract: Accurately predicting the geographic position of users can efficiently improve the quality of location-based service. To solve the problem of low prediction power of the basic Markov model and the problem of being hard to determine the order of higher order Markov model in practice, the authors present a position prediction approach based on the novel adaptive multi-order Markov model. The approach first processes the raw location information of a user based on regular shape abstraction, and automatically determines the order of the model in a heuristic way in which the heuristic is obtained from the users training data represented by a tree structure. Then, it predicts the future position of the user by using the Markov model with the most appropriate order. Finally, the performance of the adaptive multi-order Markov model is evaluated based on real location data. The results show that the prediction accuracy and prediction length of adaptive multi-order Markov model is always higher than multi-order Markov model. The average prediction accuracy is improved by nearly 20% and the average prediction length is improved by nearly 10 unit regions. Moreover, the performance of the adaptive multi-order Markov model is not apt to be influenced by the quality of training data.