Human mobility behavior is far from random, and its indicators follow non-Gaussian distributions. Predicting human mobility has the potential to enhance location-based services, intelligent transportation systems, urban computing, and so forth. In this paper, we focus on improving the prediction accuracy of non-Gaussian mobility data by constructing a hybrid Markov-based model, which takes the non-Gaussian and spatio-temporal characteristics of real human mobility data into account. More specifically, we (1) estimate the order of the Markov chain predictor by adapting it to the length of frequent individual mobility patterns, instead of using a fixed order, (2) consider the time distribution of mobility patterns occurrences when calculating the transition probability for the next location, and (3) employ the prediction results of users with similar trajectories if the recent context has not been previously seen. We have conducted extensive experiments on real human trajectories collected during 21 days from 3474 individuals in an urban Long Term Evolution (LTE) network, and the results demonstrate that the proposed model for non-Gaussian mobility data can help predicting people’s future movements with more than 56% accuracy.