We introduce and anlyze a naturally parallelizable frequency-domain method for parabolic problems with a Neumann boundary condition. After taking the Fourier transformation of given equations in the space-time domain into the space-frequency domain, we solve an indefinite, complex elliptic problem for each frequency. Fourier inversion will then recover the solution of the original problem in the space-time domain. Existence and uniqueness of a solution of the transformed problem corresponding to each frequency is established. Fourier invertibility of the solution in the frequency-domain is also examined. Error estimates for a finite element approximation to solutions fo transformed problems and full error estimates for solving the given problem using a discrete Fourier inverse transform are given.