Web mining is one of the mining technologies, which applies data mining techniques in large amount of web data to improve the web services. Web traversal pattern mining discovers most of the users? access patterns from web logs. This information can provide the navigation suggestions for web users such that appropriate actions can be adopted. However, the web data will grow rapidly in the short time, and some of the web data may be antiquated. The user behaviors may be changed when the new web data is inserted into and the old web data is deleted from web logs. Therefore, we must re-discover the user behaviors from the updated web logs. However, it is very time-consuming to re-find the users? access patterns. Hence, many researchers pay attention to the incremental mining in recent years. The essence of incremental mining is that it utilizes the previous mining results and finds new patterns just from the inserted or deleted part of the web logs such that the mining time can be reduced. In this paper, we propose an efficient incremental web traversal pattern mining algorithm. The experimental results show that our algorithm is more efficient than the other approaches.