With the rapid development of E-commerce, the topic of mining and predicting users' navigation patterns has attracted significant attention due to the wide applications like personalized services in E-commerce. Although a number of studies have been done on this topic, few of them take into account the temporal property for web user's navigation patterns. In this paper, we propose a novel method named Temporal N-Gram (TN-Gram) for constructing prediction models of Web user navigation by considering the temporality property in Web usage evolution. Moreover, three kinds of new measures are proposed for evaluating the temporal evolution of navigation patterns under different time periods. Through experimental evaluation on both of real-life and simulated datasets, the proposed TN-Gram model is shown to outperform other approaches like N-gram modeling in terms of the prediction precision, in particular when the web user's navigating behavior changes with temporal evolution.