This paper presents a genetic algorithm (GA) for Kmeans clustering. Instead of the widely applied stringof- group-numbers encoding, we encode the prototypes of the clusters into the chromosomes. The crossover operator is designed to exchange prototypes between two chromosomes. The one-step K-means algorithm is used as the mutation operator. Hence, the proposed GA is called the prototypes-embedded genetic K-means algorithm (PGKA). With the inherent evolution process of evolutionary algorithms, PGKA has superior performance than the classical K-means algorithm, while comparing to other GA-based approaches, PGKA is more efficient and suitable for large scale data sets.