Aspects of a method and system for reducing the complexity of multi-frequency hypothesis testing using an iterative approach may include estimating a frequency offset of a received signal via a plurality of iterative frequency offset hypotheses tests. The iterative frequency offset hypotheses may be adjusted for each iteration. A correlation may be done between a primary synchronization signal (PSS), and one or more frequency offset versions of a received signal to control the adjustment of the iterative frequency offset hypotheses. A frequency of the received local oscillator signal may be adjusted based on the estimated frequency offset. One or more frequency offset version of the received signal may be generated via one or more multiplication, and the multiplication may be achieved via a multiplication signal corresponding to one or more frequency offsets. The frequency offset of the received signal may be estimated via the correlation.