Abstract: Clustering is a data mining technique used to classify a number of objects into k clusters without advance knowledge such that the distance between objects within a same cluster and its center is minimised. The modelling for such problems is quite complex and searching for optimal solution usually impractical in term of computation times. Therefore, metaheuristic methods are used to find an acceptable solution within reasonable computational time. The problem addressed here provides the motivation for this work to develop a metaheuristic method to solve clustering problems. Most of previous techniques are based on K-means algorithm. However, K-means algorithm is highly depends on the initial state and very fast to get trap in local optimal solution. This work presents a modified tabu search approach to solve clustering problems that consists of two phases i.e., a constructive phase to generate an initial solution using K-means algorithm and an improvement phase, where a modified tabu search is employed with an aim to enhance the solution quality obtained from the first phase. In this study, a double tabu lists is introduced where the first tabu list is used to keep the neighbourhood structures and the second tabu list is used to keep the moves that are involved in that particular neighbourhood structure. The performance of the proposed algorithm is tested on five well-known datasets. Preliminary computational experiments are encouraging and compare positively with both the K-means and a standard tabu search alone.