Differential evolution algorithm (DE) is one of the novel stochastic optimization methods. It has a better performance in the problem of the color image quantization, but it is difficult to set the parameters of DE for users. This paper proposes a color image quantization algorithm based on self-adaptive DE. In the proposed algorithm, a self-adaptive mechanic is used to automatically adjust the parameters of DE during the evolution, and a mixed mechanic of DE and K-means is applied to strengthen the local search. The numerical experimental results, on a set of commonly used test images, show that the proposed algorithm is a practicable quantization method and is more competitive than K-means and particle swarm algorithm (PSO) for the color image quantization.