An apparatus and method for performing initial network entry in a broadband wireless communication system are provided. A communication method includes broadcasting, by a Base Station (BS), a Downlink Channel Descriptor (DCD) message including information on a different Frequency Allocation (FA) of the BS using all FAs; connecting, by one of a plurality of Media Access Control (MAC) processors of a Mobile Station (MS), using an arbitrary FA of the BS; obtaining, by the MS, information on the different FA of the BS by analyzing the DCD message received using the arbitrary FA; and performing, by one or more of the remaining MAC processors of the MS, a network entry process using the different FA of the BS according to the different FA information. Accordingly, when an MS having a plurality of MAC addresses connects to a system that performs communication through multiple FAs, different MAC processors of the MS can perform initial network entry using different FAs in the same cell (or sector or BS) without collisions.