In the Capacitated Clustering Problem, a given set of customers with distinct demands must be partitioned into p clusters with limited capacities. The objective is to find p customers, called medians, from which the sum of the distances to all other customers in the cluster is minimized. In this article, a new adaptive tabu search approach is applied to solve the problem. Initial solutions are obtained by four constructive heuristics that use weights and distances as optimization criteria. Two neighborhood generation mechanisms are used by the local search heuristic: pairwise interchange and insertion. Computational results from 20 instances found in the literature indicate that the proposed method outperforms alternative metaheuristics developed for solving this problem. © 1999 Blackwell Publishing Ltd.