A new coarse frequency offset estimation algorithm is proposed which performs robust operation in the presence of a symbol timing offset in an allowed range. The effect of a symbol timing offset on estimating a coarse frequency offset is analyzed and the coherence phase bandwidth according to the allowed symbol timing offset is introduced. In addition, a new technique for performing the coarse frequency estimation using the coherence phase bandwidth is described. Simulation results show that the proposed algorithm estimates a coarse frequency offset well under both AWGN and multipath channels even in the presence of the symbol timing offset within an allowed range.