How to effectively organize and store the profile of moving objects in a mobile environment, where then can effectively lower the paging and update cost, is an important problem in location management. Combining data mining into the mobile environment is a challenging research task, which has broad applications. Zone partition can effectively optimize the topology of location databases and efficiently reduce the cost of location paging and location update. But with the evolving time, the mobile users’ moving patterns may change, so the original partitions may not match the current moving patterns. Thus one of the important problems, which need to be solved, is how to partition the zones dynamically. Clustering method can solve the static zone partition well, but face with the dynamic zone partition problem. If the clustering method is still used to solve this problem, it means that the zones are partitioned again from scratch, which doesn’t utilize the original partitions and need great cost. In this paper an incremental clustering method is provided to solve the dynamic zone partition problem, which adjusts the original zone partitions with less cost and guarantees all the conditions needed for zone partition problem in the meanwhile.