Abstract Spectral clustering suffers from a scalability problem in both memory usage and computational time when the number of data instances N is large. To solve this issue, we present a fast spectral clustering algorithm able to effectively handle millions of datapoints at a desktop PC scale. The proposed technique relies on a kernel-based formulation of the spectral clustering problem, also known as kernel spectral clustering. In this framework, the Nystrom approximation of the feature map of size m, with m ≪ N, is used to solve the primal optimization problem. This leads to a reduction of time complexity from O(N3) to O(mN) and space complexity from O(N2) to O(mN). The effectiveness of the proposed algorithm in terms of computational efficiency and clustering quality is illustrated on several datasets.