In this paper, we study the fast algorithm for the numerical solution of the Riesz distributed-order nonlinear space-fractional diffusion equation. The finite difference method is employed to discretize the problem, the resulting system is symmetric positive definite Toeplitz matrix and then the fast Fourier transform can be used to reduce the computational cost of the matrix–vector multiplication. The preconditioned conjugate gradient method with a class of circulant preconditioners is proposed to solve the discretized linear system. Theoretically, we prove that the spectrum of the preconditioned matrix is clustering around 1, which can guarantee the superlinear convergence rate of the proposed methods. Finally, numerical experiments are carried out to demonstrate that our proposed method works very well.