Methods and apparatus for have frequency offset estimation and cell search in radio communication systems take into account the time-frequency correlation properties of reference and synchronization signals in such systems. This reduces the probability of misdetection of the physical layer cell ID and frequency offset by accounting for time-frequency ambiguities and evaluating correlation signal peaks in the frequency domain, saving signal processing time and making initial cell search considerably faster. Also, lower-grade and hence cheaper oscillators can be used without causing problems in the user's experience with a receiver, such as a cellular telephone.