The clustering problem under the criterion of minimum sum of squares clustering is a nonconvex program which possesses many locally optimal values, resulting that its solution often falls into these traps. In this paper, a hybrid tabu search based clustering algorithm called KT-Clustering is developed to explore the proper clustering of data sets. Based on the framework of tabu search, KT-Clustering gathers the optimization property of tabu search and the local search capability of K-means algorithm together. Moreover, mutation operation is adopted to establish the neighborhood of KT-Clustering. Its superiority over K-means algorithm, a genetic clustering algorithm and another tabu search based clustering algorithm is extensively demonstrated for experimental data sets.