We implemented fast Gaussian gridding (FGG)-based non-uniform fast Fourier transform (NUFFT) on the graphics processing unit (GPU) architecture for ultrahigh-speed, real-time Fourier-domain optical coherence tomography (FD-OCT). The Vandermonde matrix-based non-uniform discrete Fourier transform (NUDFT) as well as the linear/cubic interpolation with fast Fourier transform (InFFT) methods are also implemented on GPU to compare their performance in terms of image quality and processing speed. The GPU accelerated InFFT/NUDFT/NUFFT methods are applied to process both the standard half-range FD-OCT and complex full-range FD-OCT (C-FD-OCT). GPU-NUFFT provides an accurate approximation to GPU-NUDFT in terms of image quality, but offers >10 times higher processing speed. Compared with the GPU-InFFT methods, GPU-NUFFT has improved sensitivity roll-off, higher local signal-to-noise ratio and immunity to side-lobe artifacts caused by the interpolation error. Using a high speed CMOS line-scan camera, we demonstrated the real-time processing and display of GPU-NUFFT-based C-FD-OCT at a camera-limited rate of 122 k line/s (1024 pixel/A-scan).