[Objective] This paper proposes an adaptive evolutionary clustering framework for contracted customer segmentation with changing cluster structure, aiming to solve the multi-period dynamic customer segmentation problem. [Methods] The proposed framework could track customer segmentation results within a clustering cycle, which updated the proximity matrix and clustering parameters dynamically. For each clustering period, we eliminated expired clusters from the latest adjacent period based on the contract termination date. Then, we calculated the estimated proximity matrix for current customers. We also changed the exiting clusters’ structure according to data of new customers and developed guidelines to add new clusters. Finally, we examined the proposed algorithm with the updated proximity matrix and parameters to obtain the final clustering results of a specific period. [Results] The proposed framework could significantly improve the efficiency of clustering by excluding the process of selecting and matching clusters. [Limitations] The proposed algorithm was not examined with other datasets. [Conclusions] The proposed framework could effectively track evolutionary trajectories of customer groups and eliminate problems facing traditional methods. It could do multi-period dynamic segmentation for contracted customers.