In this paper, a complete solution to the initial synchronization for multi-cell OFDMA (orthogonal frequency division multiple access) systems is proposed. The proposed method consists of the following operations: timing synchronization, fractional carrier frequency offset (CFO) estimation, fractional CFO compensation, and joint integer CFO and preamble index estimation. To estimate multiple fractional CFOs with pseudoperiodic preamble, we suggest an over-sampling approach. An ill-condition detection and noise suppression algorithm is also presented. For joint integer CFO and preamble index estimation, we use a differential detection based cross-correlation method. Simulation results have shown that the proposed method gives satisfactory performance for a wide SNR range even when the mobile station (MS) is on the cell boundaries.