In this paper fast Fourier transform algorithms (FFTs) are constructed for wreath products of the form G[S n ]. Examples of interest include the hyperoctahedral groups B n (the symmetry groups of the n-cube) as well as more generally A[S n ] for any abelian groups A and also the full wreath products S m [S n ] and their iterates, often identified as automorphism groups of spherically homogeneous rooted trees. In general, direct computation of the discrete Fourier transform for any finite group H requires H 2 operations. The algorithms presented in this paper provide substantial speed-ups for general wreath products G[S n ], which for the particular examples mentioned above reduce the H 2 bound to O( H log 4 H ). Thus new classes of finite groups of close to minimal linear complexity are obtained. Applications to data analysis, signal processing and molecular spectroscopy are discussed.