In this paper, a novel technique for color clustering with application to color image segmentation is presented. Clustering is performed by applying the k-means algorithm in the L*a*b* color space. Nevertheless, Euclidean distance is not the metric chosen to measure distances, but CIEDE2000 color difference formula is applied instead. K-means algorithm performs iteratively the two following steps: assigning each pixel to the nearest centroid and updating the centroids so that the empirical quantization error is minimized. In this approach, in the first step, pixels are assigned to the nearest centroid according to the CIEDE2000 color distance. The minimization of the empirical quantization error when using CIEDE2000 involves finding an absolute minimum in a non-linear equation and, therefore, an analytical solution cannot be obtained. As a consequence, a heuristic method to update the centroids is proposed. The proposed algorithm has been compared with the traditional k-means clustering algorithm in the L*a*b* color space with the Euclidean distance. The Borsotti parameter was computed for 28 color images. The new version proposed outperformed the traditional one in all cases.