We present a fast iterative fast Fourier transform (FFT) based reconstruction algorithm that allows for non-parallel redshift-space distortions (RSDs). We test our algorithm on both N-body dark matter simulations and mock distributions of galaxies designed to replicate galaxy survey conditions. We compare solenoidal and irrotational components of the redshift distortion and show that an approximation of this distortion leads to a better estimate of the real-space potential (and therefore faster convergence) than ignoring the RSD when estimating the displacement field. Our iterative reconstruction scheme converges in two iterations for the mock samples corresponding to Baryon Oscillation Spectroscopic Survey CMASS Data Release 11 when we start with an approximation of the RSD. The scheme takes six iterations when the initial estimate, measured from the redshift-space overdensity, has no RSD correction. Slower convergence would be expected for surveys covering a larger angle on the sky. We show that this FFT based method provides a better estimate of the real-space displacement field than a configuration space method that uses finite difference routines to compute the potential for the same grid resolution. Finally, we show that a lognormal transform of the overdensity, used as a proxy for the linear overdensity, is beneficial in estimating the full displacement field from a dense sample of tracers. However, the lognormal transform of the overdensity does not perform well when estimating the displacements from sparser simulations with a more realistic galaxy density.