A spectrally accurate method for the fast evaluation of N-particle sums of the periodic Stokeslet is presented. Such sums occur in boundary integral- and potential methods for viscous flow problems. Two different decomposition methods, leading to one sum in real space and one in reciprocal space, are considered. An FFT based method is applied to the reciprocal part of the sum, using convolutions with a Gaussian function to place the point sources on a grid. Due to the spectral accuracy of the method, the grid size needed is low and also in practice, for a fixed domain size, independent of N. The leading cost therefore arise from the to-grid and from-grid operations, that are linear in N. Combining this FFT based method for the reciprocal sum with the direct evaluation of the real space sum, a spectrally accurate algorithm with a total complexity of O(N log N) is obtained.