A method for performing an initial operation of a mobile station (MS) that uses a first frequency band, in a frequency overlay communication system having the first frequency band including a plurality of sub-frequency bands. The method includes performing correlation on a full frequency band in units of the first frequency band, receiving broadcast information through a frequency band having a maximum correlation value, and performing an initial access to a base station (BS) through the frequency band having the maximum correlation value if a frequency bandwidth of the BS acquired from the broadcast information is narrower than or equal to a selected frequency bandwidth of the MS.