Synchronization methods and systems for communications over a multi-band system are presented. A synchronization technique for communications over a multi-band system includes receiving a packet of preamble symbols respectively transmitted over a sequence of frequency sub-bands according to one of a plurality of frequency hopping patterns, wherein the plurality of frequency hopping patterns are partitioned into a plurality of disjoint groups, each group having a different associated periodicity; computing, in parallel, respective autocorrelation values of the packet received in a selected frequency sub-band at a plurality of symbol delays; and selecting one of the plurality of groups of frequency hopping patterns based on the autocorrelation values at the plurality of symbol delays.