As one of the most widely used clustering techniques, the fuzzy K-Means (also called FKM or FCM) assigns every data point to each cluster with a certain degree of membership. However, conventional FKM approach relies on the square data fitting term which is not robust to data outliers and ignores the prior information, which leads to unsatisfactory clustering results. In this paper, we present a novel and robust fuzzy K-Means clustering algorithm, namely Embedding Fuzzy K-Means with Nonnegative Spectral Clustering via Incorporating Side Information. The proposed method combines fuzzy K-Means with nonnegative spectral clustering into a unified model, and further takes the advantage of the prior knowledge of data pairs such that the quality of similarity graph is enhanced and the clustering performance is effectively improved. Besides, the l2,1-norm loss function is adopted in the objective function, which achieves better robustness to outliers. Last, experimental results on benchmark datasets verify the effectiveness and superiority of the proposed clustering method. © 2018 Association for Computing Machinery.