Orthogonal frequency-division multiplexing multiple access (OFDMA) has been considered as a promising multiple access technique in OFDM-based communication systems. In the system, all users share subcarriers in a frequency-division multiplexing manner. Similar to OFDM systems, the carrier frequency offset (CFO) will induce inter-carrier interference (ICI) degrading the system performance seriously. However, since the CFO for each user may be different, the compensation turns out much more complicated than that in OFDM systems. A simple method to this problem is the use of a direct zero-forcing (ZF) method which involves the inverse of a matrix. The required computational complexity becomes prohibitively high when the number of subcarriers is large. In this paper, we propose a low-complexity method to overcome the problem in an interleaved uplink OFDMA system. We explore the special structure of the CFO-induced interference matrix and develop a method to solve the matrix inversion problem with fast Fourier transform (FFT). The proposed method can reduce the required computational complexity from O(Nc
3) to O(N clog2Nc). From the simulations, we can see that the proposed method can perform as well as that of the direct ZF method while the required complexity is much lower.