The kernel fuzzy clustering algorithms can explore the non-linear relations of pixels in an image. However, most of kernel-based methods are computationally expensive for color image segmentation and neglect the inherent locality information in images. To alleviate these limitations, this paper proposes a novel kernel fuzzy clustering framework for fast color image segmentation. More specifically, we first design a new superpixel generation method that uses random Fourier maps to approximate Gaussian kernels and explicitly represent high-dimensional features of pixels. Clustering superpixels instead of large-sized pixels speeds up the segmentation of a color image significantly. More importantly, the features of superpixels used by fuzzy clustering are also calculated in the approximated kernel space and the local relationships between superpixels are depicted as a graph prior and appended into the objective function of fuzzy clustering as a Kullback–Leibler divergence term. This results in a new fuzzy clustering model that can further improve the accuracy of the image segmentation. Experiments on synthetic and real-world color image datasets verify the superiority and high efficiency of the proposed approach.