As a total amount of traffic data in networks has been growing at an alarming rate, many researches to mine traffic data with the purpose of getting useful information are currently being performed. However, since network traffic data contain the information about Internet usage patterns of users, network users’ privacy can be compromised during the mining process. In this paper, we propose an efficient and practical method for privacy preserving sequential pattern mining on network traffic data. In order to discover frequent sequential patterns without violating privacy, our method uses the N-repository server model that operates as a single mining server and the retention replacement technique that changes the answer to a query probabilistically. In addition, our method accelerates the overall mining process by maintaining the meta tables in each site. Extensive experiments with real-world network traffic data revealed the correctness and the efficiency of the proposed method.