In this paper, a fast algorithm is proposed for solving distributed-order time-space fractional diffusion equations. Integral terms in time and space directions are discretized by the Gauss-Legendre quadrature formula. The Caputo fractional derivatives are approximated by the exponential-sum-approximation method, and the finite difference method is applied for spatial approximation. The coefficient matrix of the discretized linear system is symmetric positive definite and possesses block-Toeplitz-Toeplitz-block structure. The preconditioned conjugate gradient method with a block-circulant-circulant-block preconditioner is employed to solve the linear system. Theoretically, the stability and convergence of the proposed scheme are discussed. Numerical experiments are carried out to demonstrate the effectiveness of the scheme.